問題はこちら
No.286 Modulo Discount Store - yukicoder
yukicoder No.90 品物の並び替え - メモ
これと同様にしてbitDP
ほとんど同じなので通常解説は省略
int main(){ int d[99999]={},a[20],i,j,k,n,m; scanf("%d",&n); for(i=0;i<n;i++)scanf("%d",a+n); for(i=0;i<1<<n;i++){ //既に買った商品のbitが立っている for(j=0;j<n;j++){ //j番目の商品を新たに買う(jは0-based) if(i>>j&1)continue; for(m=k=0;k<n;k++)m=(m+(i>>k&1)*a[k])%1000; //既に買った商品の合計金額を求めて m=a[j]<m?0:a[j]-m; //a[j]番目の商品の割引後の価格を求め !d[i^1<<j]|d[i^1<<j]>d[i]+m?d[i^1<<j]=d[i]+m:0; //更新できるかチェック } } i=!printf("%d",d[(1<<n)-1]); }
まずはいつもの
d[99999],a[20],i=65536,j,k,n; main(m){ for(gets(a);~scanf("%d",a+j++);); for(;i--;) for(j=16;j--;m=a[j]<m?0:a[j]-m,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0) for(m=0,k=16;k--;m%=1000)m+=(~i>>k&1)*a[k]; //既に買った商品を再度買ったら高くつくのは当たり前なのでチェックを省略 i=!printf("%d",*d); }
213B
for圧縮
for(;i--;)for(j=16;j--;m=a[j]<m?0:a[j]-m,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0)for(m=0,k=16;k--;m%=1000)m+=(~i>>k&1)*a[k]; for(;i--;)for(j=15;k--?m=(m+(~i>>k&1)*a[k])%1000,1:(m=a[j]<m?0:a[j]-m,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0,m=0,k=16,j--);); for(;k--?m=(m+(~i>>k&1)*a[k])%1000,1:(m=a[j]<m?0:a[j]-m,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0,m=0,k=16,j--)?:(j=15,i--);); //最初にmが0になっている必要がある
んんん?縮まない?
細かなバリエーションも考えたけれどどれも同じ長さにしかならなかった
for(;k--?m=(m+(~i>>k&1)*a[k])%1000,1:(m=a[j]<m?0:a[j]-m,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0,m=0,k=16,j--)?:(j=15,i--);); for(;k--?m=(m+(~i>>k&1)*a[k])%1000,1:(m=a[j]<m?0:a[j]-m,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0,m=0,k=16,!j--?j=15,i--:1);); for(;k--?m=(m-(~i>>k&1)*a[k])%1000,1:(m+=a[j],m<0?m=0:0,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0,m=0,k=16,!j--?j=15,i--:1););
scanfのfor文と合体させると、scanfが多いせいでTLEになる
悲しいので圧縮する前ので提出した