yukicoder No.247 線形計画問題もどき

問題は次のように読み替えられる
「a[i]円玉がたくさんあるとき、ちょうどC円を払うために必要な硬貨の枚数は最小でいくらか？」
ということで配るDPで書くことができる

#define inf 1000000
//解が存在すればそれはC以下なのでCより大きな値をおく
int main(){
	int a[110],x[100010],i,j,n,c,t;
	scanf("%d%d",&c,&n);
	for(i=0;i<n;i++)scanf("%d",a+i);
	for(i=0;i<100010;i++)x[i]=inf;
	x[0]=0;
	//0円は0枚で払える
	for(i=0;i<c;i++){
	//a[i]円玉の使用を順次解禁して配るDP
		for(j=0;j<n;j++)if(x[i]!=inf){
			t=i+a[j];
			if(t<=c&&x[t]>x[i]+1)x[t]=x[i]+1;
			//j円がx[j]枚で払えるとき、j+a[i]円はx[j]+1枚で払える
		}
	}
	printf("%d",x[c]==inf?-1:x[c]);
	//x[c]がinfのままならc円を払うことは出来ない
	return 0;
}

配列の初期値を0にする
配り始めの起点が必要なので、x[0]に1を入れることで、実際の値+1を配列に保存していく
これにより最後の出力がx[c]-1とまとめられる
またa[i]を配列で保存する必要はなく、随時配ればいいので短縮できる
更にNの読み飛ばしも、x[0]の初期化との順番に気をつければまとめることができる
また配列サイズを2倍にすることで範囲外チェックをサボる

x[1<<18],c,i;
main(j){
	for(scanf("%d",&c);~scanf("%d",&j);*x=1)for(i=0;i<c;i++)x[i]&&!x[i+j]|x[i+j]>x[i]?x[i+j]=x[i]+1:0;
	i=!printf("%d",x[c]-1);
}

ポインタを使って

x[1<<18],c,*p;
main(j){
	for(scanf("%d",&c);~scanf("%d",&j);*x=1)for(p=x;p-x<c;p++)*p&&!p[j]|p[j]>*p?p[j]=1+*p:0;
	c=!printf("%d",x[c]-1);
}

134B

メモ

yukicoderでゆるふわgolf

yukicoder No.247 線形計画問題もどき