問題はこちら
No.90 品物の並び替え - yukicoder
制約的に全探索すればいいだけなのだけど、Cにはnext_permutation的なものはないし
自分で実装するのは面倒なので、先に解いていたNo.357をコピペした
いわゆるbitDPと呼ばれている奴
「既に使った商品」をbitで保存して値の小さい方から配るDPをしていく
この配列には「既に使った商品」を先頭から適当に並べた時に得られる最適な点が保存されていく
なぜなら状態の遷移先は常にbitの値が大きくなるからである
（例えばdp[i]がもらうのはiよりも値が小さいところからのみなのでdp[i]から配るときには、ここは最適の値になっている）
イメージしにくいので具体的に。
例えばN=6とし、「既に使った商品の集合」を{2,3,5}とする
（商品のindexは1-basedとする）
==配る側のイメージ==
3番目の商品までは2,3,5で決まっているので「4番目の商品として何を置くか」を考える
1を選ぶとすると、これによりΣ[k=2,3,5]score[k][1]の点が確定する
よってdp[{1,2,3,5}]の値を(必要なら) dp[{2,3,5}]+Σ[k=2,3,5]score[k][1] で更新する
同様にdp[{2,3,4,5}],dp[{2,3,5,6}]にも値を配る
==もらう側のイメージ==
dp[{1,2,3,5}]はdp[{2,3,5}],dp[{1,3,5}],dp[{1,2,3}]から値をもらう
dp[{2,3,5}]から値をもらうときは
<2,3,5の並び>,1
という並びになるが、{1,2,3,5}を使い、かつ、1を4番目に使った時のscoreは、前3つを適当に並べている時に最大になる
なのでこのときもらう値は「4番目を1にするとき」の条件付きで最大
同様に他からもらう時も「4番目をhogeにするとき」の条件付きで最大なので
それら全てにわたってmaxを取れば全体で最大となるものが得られる
実装
int main(){ int d[512]={},s[9][9]={},i,j,u,v,x,n; scanf("%d%d",&n,&x); while(x--){ scanf("%d%d%d",&i,&j,&u); s[i][j]=u; } for(x=0;x<1<<n;x++){ //xが使用済みの商品の状態を表すbit //下からibit目(0-based)が立っていれば、商品iは使用済み for(i=0;i<n;i++){ //次に置く商品として商品iを選ぶ if(x&1<<i)continue; //使用済みなら選び直し u=d[x]; for(j=0;j<n;j++)if(x&1<<j)u+=s[j][i]; //そうでないなら、使用済みの商品に起因する点を加算して if(d[v=x|1<<i]<u)d[v]=u; //配る } } printf("%d",d[(1<<n)-1]); //すべての商品を使った時の値 return 0; }
まずはわかりやすいところ
d[512],s[9][9],i,j,u,v,x; main(n){ for(n=atoi(gets(&n));~scanf("%d%d%d",&i,&j,&u);s[i][j]=u); for(;x<1<<n;x++)for(i=0;i<n;d[v=x|1<<i]<u?d[v]=u:0,i++)for(u=d[x],j=0;~x&1<<i&&j<n;j++)u+=x&1<<j?s[j][i]:0; i=!printf("%d",d[x-1]); }
1個ずつfor文潰すよ
1段階目
for(i=0;i<n;d[v=x|1<<i]<u?d[v]=u:0,i++)for(u=d[x],j=0;~x&1<<i&&j<n;j++)u+=x&1<<j?s[j][i]:0; for(i=n;i--;d[v=x|1<<i]<u?d[v]=u:0)for(u=d[x],j=n;~x&1<<i&&j--;u+=x&1<<j?s[j][i]:0); for(i=n;i--;d[v=x|1<<i]<u?d[v]=u:0)for(u=d[x],j=n;~x&!!j--<<i;u+=x&1<<j?s[j][i]:0); //↓形式的に書き換え for(i=n;~x&!!j--<<i?u+=x&1<<j?s[j][i]:0:(d[v=x|1<<i]<u?d[v]=u:0,u=d[x],j=n,i--);); //このままだと途中で0になって困る可能性がある //元のfor文において、d[v]の値の更新をjのループ内に持ってきても大丈夫、つまり for(i=0;i<n;d[v=x|1<<i]<u?d[v]=u:0,i++)for(u=d[x],j=0;~x&1<<i&&j<n;j++)u+=x&1<<j?s[j][i]:0 for(i=0;i<n;i++)for(u=d[x],j=0;~x&1<<i&&j<n;d[v=x|1<<i]<u?d[v]=u:0,j++)u+=x&1<<j?s[j][i]:0 //としてよいので for(i=n;~x&!!j--<<i?u+=x&1<<j?s[j][i]:0,d[v=x|1<<i]<u?d[v]=u:1:(u=d[x],j=n,i--);); //これで解決 //ただしiがnのときも実行され、n=9のときこのときs[j][i]がやばそうなのでs[i][j]に変えておく //（これは商品を後ろから並べていったと考えられる） //さらにdも倍のサイズが必要になり1B増える //i=n-1とすると2B増えるのでしょうがない
2段階目、3段階目
for(;x<1<<n;x++)for(i=n;~x&!!j--<<i?u+=x&1<<j?s[i][j]:0,d[v=x|1<<i]<u?d[v]=u:1:(u=d[x],j=n,i--);); for(x=-1;~x&!!j--<<i?u+=x&1<<j?s[i][j]:0,d[v=x|1<<i]<u?d[v]=u:1:!(u=d[x],j=n,i--)?i=n,++x<1<<n:1;); //1B増えたが、for文が1つになったことが重要 for(n=atoi(gets(&n));~scanf("%d%d%d",&i,&j,&u);s[i][j]=u);for(x=-1;~x&!!j--<<i?u+=x&1<<j?s[i][j]:0,d[v=x|1<<i]<u?d[v]=u:1:!(u=d[x],j=n,i--)?i=n,++x<1<<n:1;); for(n=atoi(gets(&n));~scanf("%d%d%d",&i,&j,&u)?s[i][j]=u:~x&!!j--<<i?u+=x&1<<j?s[i][j]:0,d[v=x|1<<i]<u?d[v]=u:1:!(u=d[x],j=n,i--)?i=n,++x<1<<n:1;);
ここまでのまとめ
d[1100],s[9][9],i,j,u,v,x=-1; main(n){ for(n=atoi(gets(&n));~scanf("%d%d%d",&i,&j,&u)?s[i][j]=u:~x&!!j--<<i?u+=x&1<<j?s[i][j]:0,d[v=x|1<<i]<u?d[v]=u:1:!(u=d[x],j=n,i--)?i=n,++x<1<<n:1;); i=!printf("%d",d[x-1]); }
dのindexを逆にしよう
つまり「既に使った商品」ではなく「まだ使ってない商品」をbitで保存
そうすれば出力がちょっと簡単に
さらに最初に問題になっていたiが9のときの処理が解決
d[513],s[9][9],i,j,u,v,x; main(n){ for(n=atoi(gets(&n)),x=1<<n;~scanf("%d%d%d",&i,&j,&u)?s[i][j]=u:x&!!j--<<i?u+=x&1<<j?0:s[i][j],d[v=x^1<<i]<u?d[v]=u:1:!(u=d[x],j=n,i--)?i=n,x--:1;); i=!printf("%d",*d); }
nいらなくない？
d[513],s[9][9],i,j,u,x=512; main(v){ for(gets(&v);~scanf("%d%d%d",&i,&j,&u)?s[i][j]=u:x&!!j--<<i?u+=x&1<<j?s[j][i]:0,d[v=x^1<<i]<u?d[v]=u:1:!(u=d[x],j=9,i--)?i=9,x--:1;); i=!printf("%d",*d); }
188B
