题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1300
思路：直接写递推方程式：dp[i]=min{dp[j]+value}（0<=j<i， value为第j+1类珠宝到第i类全部以i类买入的价值; );然后我们可以用一个数组记录一下0-i的花费
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define MAXN 1111 7 #define inf 1<<30 8 int cost[MAXN]; 9 int dp[MAXN]; 10 int a[MAXN],b[MAXN]; 11 12 int main(){ 13 int _case,n; 14 scanf("%d",&_case); 15 while(_case--){ 16 scanf("%d",&n); 17 memset(cost,0,sizeof(cost)); 18 for(int i=1;i<=n;i++){ 19 scanf("%d%d",&a[i],&b[i]); 20 cost[i]=cost[i-1]+a[i]; 21 } 22 for(int i=1;i<=n;i++)dp[i]=inf; 23 dp[0]=0; 24 for(int i=1;i<=n;i++){ 25 for(int j=0;j<i;j++){ 26 dp[i]=min(dp[i],dp[j]+(cost[i]-cost[j]+10)*b[i]); 27 } 28 } 29 printf("%d\n",dp[n]); 30 } 31 return 0; 32 }