题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1300
就是要明白 一些东西的的数量的累加肯定是连续的 比如 不可能a2累加到a4,跳过a3,而应该是a2,a3 都累加到a4
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=200+5;
const int INF=0x3f3f3f3f;
int d[maxn],sum[maxn];
//d[i]表示前i个最低价格
int main(int argc, char const *argv[])
{int T,num,price; cin>>T;while(T--){int n; cin>>n;memset(d,INF,sizeof(d));d[0]=sum[0]=0;for (int i = 1; i <= n; ++i){scanf("%d%d",&num,&price);sum[i]=num+sum[i-1];d[i]=min(d[i-1]+(num+10)*price,(sum[i]+10)*price);for (int j = 1; j < i; ++j)d[i]=min(d[i],d[j]+(sum[i]-sum[j]+10)*price);}cout<<d[n]<<endl;}return 0;
}