Luogu

這可能是繼數字金字塔后IOI最水的一道題了。（然而我也就只能做這種水題

設\(dp[i,j]\)表示第\(i\)行選到第\(j\)個最優解，狀態轉移方程很顯然，如下

\[dp[i,j]=\max_{i-1\le k<j}\{dp[i-1,k]+A[i,j]\}\]

其中\(A[i,j]\)表示的是第\(i\)束花插♂在第\(j\)個花盆中的美學值。

然后一個sb喜聞樂見的因為沒有發現有負權值而wa50了無數次

#include <bits/stdc++.h>const int max_n=1000+5; const int inf=0x3f3f3f3f;int N,M,Ans=-inf,Ansi; int A[max_n][max_n],dp[max_n][max_n],last[max_n][max_n];inline int read() {register int x=0,v=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-') v=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar(); }return x*v; }void out(int x,int y) {if(x!=1) out(x-1,last[x][y]);printf("%d ",y); }int main() {N=read(),M=read();for(int i=1;i<=N;++i)for(int j=1;j<=M;++j)A[i][j]=read();memset(dp,-inf,sizeof(dp));dp[0][0]=0;for(int i=1;i<=N;++i){for(int j=i;j<=M-N+i;++j){for(int k=i-1;k<j;++k){if(dp[i][j]<dp[i-1][k]+A[i][j]){dp[i][j]=dp[i-1][k]+A[i][j];last[i][j]=k;} }}}for(int i=N;i<=M;++i)if(Ans<dp[N][i]) Ans=dp[N][i],Ansi=i;printf("%d\n",Ans);out(N,Ansi);return 0; }

轉載于:https://www.cnblogs.com/zcdhj/p/8407378.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的IOI1999 花店橱窗布置的全部內容，希望文章能夠幫你解決所遇到的問題。

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