題目鏈接：http://poj.org/problem?id=1260

　　基本DP，只要證明最優解中不會有交叉替換，得出轉移方程：f[i]=min{f[j]+(a[j+1]+..+a[i]+10)*p[i]}。由(ai+10)*bi+(aj+10)*bj=(ai+aj+10)*bj ?==> ?(ai+10)*bi=ai*bj ? ?替換==> ?t*bi=ai*bj 可證。

1 //STATUS:C++_AC_0MS_176KB 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<string.h> 5 #include<math.h> 6 #include<iostream> 7 #include<string> 8 #include<algorithm> 9 #include<vector> 10 #include<queue> 11 #include<stack> 12 using namespace std; 13 #define LL __int64 14 #define pii pair<int,int> 15 #define Max(a,b) ((a)>(b)?(a):(b)) 16 #define Min(a,b) ((a)<(b)?(a):(b)) 17 #define mem(a,b) memset(a,b,sizeof(a)) 18 #define lson l,mid,rt<<1 19 #define rson mid+1,r,rt<<1|1 20 const int N=110,INF=0x3f3f3f3f,MOD=1999997; 21 const LL LLNF=0x3f3f3f3f3f3f3f3fLL; 22 23 int num[N],w[N],f[N]; 24 int T,n; 25 26 int main() 27 { 28 // freopen("in.txt","r",stdin); 29 int i,j,k,t; 30 scanf("%d",&T); 31 while(T--) 32 { 33 scanf("%d",&n); 34 f[0]=0; 35 for(i=1;i<=n;i++) 36 scanf("%d%d",&num[i],&w[i]); 37 for(i=1;i<=n;i++){ 38 f[i]=INF; 39 for(j=0;j<i;j++){ 40 for(t=10,k=j+1;k<=i;k++) 41 t+=num[k]; 42 f[i]=Min(f[i],f[j]+t*w[i]); 43 } 44 } 45 46 printf("%d\n",f[n]); 47 } 48 return 0; 49 }

?

轉載于:https://www.cnblogs.com/zhsl/archive/2013/01/20/2868240.html

總結

以上是生活随笔為你收集整理的POJ-1260 Pearls DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。