用w[i][j]表示i到j之間沒有邊毀掉的費用。
有一種很好證明w[i][j]是否滿足四邊形不等式的條件. 若(w[i+1][j]-w[i][j])是關於j的減函數,就是滿足條件的。可以證明這裡的w[i][j]是瞞住條件的。
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int inf = 0x3fffffff; const int mmax =1010; int w[mmax]; int sum[mmax]; int f[mmax]; int dp[mmax][mmax]; int S[mmax][mmax]; int cost[mmax][mmax]; int main() { int n,m; while(cin>>n>>m && n+m) { w[0]=0; sum[0]=0; f[0]=0; for(int i=1;i<=n;i++) { scanf(%d,&w[i]); sum[i]=sum[i-1]+w[i]; f[i]=sum[i]*w[i]+f[i-1]; } for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) cost[i][j]=(sum[j-1]-sum[i-1])*sum[j]-(f[j-1]-f[i-1]); dp[0][0]=0; for(int i=1;i<=n;i++) { dp[0][i]=cost[1][i]; S[0][i]=0; } for(int i=1;i<=m;i++) { dp[i][0]=0; S[i][n+1]=n; for(int j=n;j>=1;j--) { dp[i][j]=inf; int l=S[i-1][j],r=S[i][j+1]; for(int k=l;k<=min(j-1,r);k++) { if(dp[i][j]>dp[i-1][k]+cost[k+1][j]) { dp[i][j]=dp[i-1][k]+cost[k+1][j]; S[i][j]=k; } } } } printf(%d ,dp[m][n]); } return 0; }
一.題目描述Write a program to solve
uva 757 Gone Fishing &nbs
第一次參加藍橋杯,也是有很多感觸的,時間完全不夠寫最後一題.
題目: You are given an n x
Wolf and Rabbit Time Limit:
問題描述有7對數字:兩個1,兩個2,兩個3,...兩個7,把