PKU 1505 Copying Books
http://poj.org/problem?id=1505
m個の数列が与えられる。
この時、これを連続するk個の区間に分割して、それぞれの和の最大値が最小になるような分割の仕方を出力しろというような問題。
出力の仕方がいくつかある場合は、先頭に近い区間ほど要素が少なくなるようにする。
メモ化再帰しました。
今日の最初に解いた問題(PKU 3638)と結構似ている気がします。
この問題は4ヶ月くらい前に開いて動的計画法的な問題だと思っていたのですが、全然答え方が分からなくて困っていたのですが、Moogleのお陰で解き方が分かった気がします。
出力の時に、先頭に近い区間の要素を少なくするという部分がおかしくてWAをもらいました。
bool vis[600][600]; ll memo[600][600]; int pa[600]; ll sum[600]; ll rec(int re,int ed){ //cout<<re<<' '<<ed<<endl; if(re==0)return sum[ed+1]; if(vis[re][ed])return memo[re][ed]; vis[re][ed]=true; ll& ret=memo[re][ed]=1LL<<60LL; for(int i=re-1;i<ed;++i) ret=min(ret, max(sum[ed+1]-sum[i+1],rec(re-1,i))); //cout<<re<<' '<<ed<<' '<<ret<<endl; return ret; } int m,k; void out(int re,int ed,ll va){ if(re==0){ rep(i,ed+1) cout<<pa[i]<<' '; if(ed+1<m)cout<<"/ "; else cout<<endl; return; } //cout<<re<<' '<<ed<<' '<<memo[re][ed]<<endl; for(int i=re-1;i<ed;++i){ //cout<<sum[ed+1]-sum[i+1]<<' '<<rec(re-1,i)<<endl; if(va>=max(sum[ed+1]-sum[i+1],rec(re-1,i))){ out(re-1,i,va); for(int j=i+1;j<=ed;++j) cout<<pa[j]<<' '; if(ed+1<m)cout<<"/ "; else cout<<endl; return; } } } void solve(){ scanf("%d%d",&m,&k); rep(i,m){ scanf("%d",pa+i); sum[i+1]=sum[i]+pa[i]; } memset(vis,0,sizeof(vis)); ll va=rec(k-1,m-1); out(k-1,m-1,va); } main(){ int t; scanf("%d",&t); while(t--) solve(); }