Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
简单DP,0MS#include<cstdio> #include<cstring> #include<algorithm> #define inf 9999999 using namespace std; struct kk { int a; int p; int sum; }r[200]; int dp[200]; int main() { int t,n,i,j; scanf("%d",&t); while(t--) { memset(dp,inf,sizeof(dp)); scanf("%d",&n); r[0].sum=0; for(i=1;i<=n;i++) { scanf("%d%d",&r[i].a,&r[i].p); r[i].sum=r[i-1].sum+r[i].a; } dp[0]=0; for(i=1;i<=n;i++) for(j=0;j<i;j++) dp[i]=min(dp[i],(r[i].sum-r[j].sum+10)*r[i].p+dp[j]); printf("%d\n",dp[n]); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator