首页 > 代码库 > HDU 1300
HDU 1300
http://acm.hdu.edu.cn/showproblem.php?pid=1300
这题大一就看到过,当时没读懂题目,今天再做就容易多了
题意:升序给出n个珍珠的的数量和价值,问买这些珍珠的最小花费,其中可以用价值高的珍珠等量代替价值小的珍珠,并且一种价钱如果决定买,必须多买10个保底
水dp,dp[i]表示买前i种珍珠的最小花费,枚举代替的区间
#include <iostream>#include <cstdio>#include <cstring>#include <set>#include <cmath>using namespace std;int dp[105],a[105],p[105];int main(){ int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); for(int i=1;i<105;i++)dp[i]=0xfffffff; for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&p[i]); dp[1]=(a[1]+10)*p[1]; for(int i=2;i<=n;i++){ for(int j=1;j<=i;j++){ int res=dp[j-1]; int cnt=0; for(int k=j;k<=i;k++){ cnt+=a[k]; } res+=(cnt+10)*p[i]; dp[i]=min(dp[i],res); } } printf("%d\n",dp[n]); } return 0;}
HDU 1300
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。