問題はこちら
No.27 板の準備 - yukicoder
作りたい板の長さが30以下なので用意する板の長さも30以下
ということは用意する3種類の板の長さの組として考えられるものは30C3=4060通り
各場合について、何枚用意すればいいかDPで調べる
int main(){ int d[70],a[4],i[3],j,m=120,t; //120は自明な上界。長さ1の板が120枚あれば必ず作れる for(j=0;j<4;j++)scanf("%d",a+j); for(i[0]=1;i[0]<31;i[0]++)for(i[1]=i[0]+1;i[1]<31;i[1]++)for(i[2]=i[1]+1;i[2]<31;i[2]++){ for(t=1;t<70;t++)d[t]=9999; //dの初期化はmの初期値以上で d[0]=0; for(t=0;t<31;t++){ for(j=0;j<3;j++)if(d[t+i[j]]>d[t])d[t+i[j]]=d[t]+1; } //配るDP t=0; for(j=0;j<4;j++)t+=d[a[j]]; m=m>t?t:m; } printf("%d",m); return 0; }
3重ループウザいのでこの部分を
for(i=1;i<27000;i++)
に書きかえ、i[0],i[1],[2]の代わりにi%30,i/30%30,i/900を使う
(この3数には重複や0が含まれるが影響はない)
……と思ったけど、0~30という5bitの情報しか無いんだからもうちょっと簡単に
for(i=1;i<1<<15;i++)
としてi[x]の代わりに(i>>5*x)&31を使う
(こんどは31も含まれることになるが、31の板を使うことはありえないので、これも影響はない)
更に、入力として考えられるもの30^4通りを全て確かめたところ、出力は最大で9にしかならない
なので初期値の文字数も削減
d[70],a[4],i=1<<15,j,m=9; main(t){ for(;~scanf("%d",a+j++);); for(;--i;){ for(t=70;--t;d[t]=9); for(t=0;t<31;t++)for(j=3;j--;)d[t+(i>>5*j&31)]>d[t]?d[t+(i>>5*j&31)]=d[t]+1:0; for(t=j=0;j<4;t+=d[a[j++]]); m=m>t?t:m; } j=!printf("%d",m); }
出力が1文字ならputcharすればよくね?
d[70],a[4],i=1<<15,j,m=57; main(t){ for(;~scanf("%d",a+j++);); for(;--i;){ for(t=31;--t;d[t]=9); for(;t<31;t++)for(j=3;j--;)d[t+(i>>5*j&31)]>d[t]?d[t+(i>>5*j&31)]=d[t]+1:0; for(;++j<4;t+=d[a[j]]+4); m=m>++t?t:m; } j=!putchar(m); }
DPしてるfor文を抜けたところでt=31になっているので
実際の和+4を加算していくことで、真値+47が保存される
最後にダメ押しの前置incで0のとき48になるようにつじつまを合わせる
ところでループの終わりの時点ではt>31なのに、またt=31をセットするのは冗長だよなあ
最初の1回さえ乗り切れば1B縮みそう
初期値を与えるためにtとjを入れ替えてみる
d[99],a[5],i=1<<20,t=31,m=57; main(j){ for(;~scanf("%d",a+j++);); for(;--i;){ for(;--t;d[t]=9); for(;t<31;t++)for(j=4;--j;)d[t+(i>>5*j&31)]>d[t]?d[t+(i>>5*j&31)]=d[t]+1:0; for(;++j<5;t+=d[a[j]]+4); m=m>++t?t:m; } t=!putchar(m); }
jの初期値が1になったせいでaの読み込みが1個ずれ、
iを5つシフトしたため時間が32倍かかるようになったけどまだ余裕
dの初期化をするときのtの値は最大で48+4*9=84になるのでdのサイズを大きくした
あと代入のところ長いからポインタ使おう
d[99],a[5],i=1<<20,t=31,m=57,*p; main(j){ for(;~scanf("%d",a+j++);); for(;--i;){ for(;--t;d[t]=9); for(;t<31;t++)for(j=4;--j;)*(p=d+t+(i>>5*j&31))>d[t]?*p=d[t]+1:0; for(;++j<5;t+=d[a[j]]+4); m=m>++t?t:m; } t=!putchar(m); }
ループ圧縮
d[99],a[5],i=1<<20,t=31,m=57,*p; main(j){ for(;~scanf("%d",a+j++);); for(;--i;m=m>++t?t:m){ for(;--t;d[t]=9); for(;--j?*(p=d+t+(i>>5*j&31))>d[t]?*p=d[t]+1:1:(j=4*(++t<31));); for(;++j<5;t+=d[a[j]]+4); } t=!putchar(m); }
ループ終了時のtの値を32にできるようになった やったね
d[99],a[5],i=1<<20,t=31,m=57,*p; main(j){ for(;~scanf("%d",a+j++);); for(;--i;m=m>t?t:m){ for(;--t;d[t]=9); for(;--j?*(p=d+t+(i>>5*j&31))>d[t]?*p=d[t]+1:1:(j=4*(t++<31));); for(;++j<5;t+=d[a[j]]+4); } t=!putchar(m); }
208B
16/07/15追記
出力でちょっと縮む
d[99],a[5],i=1<<20,t=31,m=57,*p; main(j){ for(;~scanf("%d",a+j++);); for(;--i;m=m>t?t:m){ for(;--t;d[t]=9); for(;--j?*(p=d+t+(i>>5*j&31))>d[t]?*p=d[t]+1:1:(j=4*(t++<31));); for(;++j<5;t+=d[a[j]]+4); } t=!puts(&m); }
206B