問題はこちら
No.496 ワープクリスタル (給料日前編) - yukicoder
DPやるだけ
#define min(p,q)(p<q?p:q) d[110][110]; x,y,n,f,a,b,c,t; main(){ scanf("%d%d%d%d",&x,&y,&n,&k); //初期化 for(int p=0;p<=x;p++)for(int q=0;q<=y;q++)d[p][q]=(p+q)*f; while(n--){ scanf("%d%d%d",&a,&b,&c); //1度しか使えないので大きい方から配る for(int p=x;p>=a;p--)for(int q=y;q>=b;q--)d[p][q]=min(d[p][q],d[p-a][q-b]+c); } printf("%d",d[x][y]); }
下準備にd[p][q]に(p+q)*fを配るのと、DPのループにまとめてしまえるように調整
まだまだ無駄が多そうだけどちょっとゴルフする気力がない
d[110][110];a,b,c,x,y,n,k,p,q,t; main(i){ for(scanf("%d%d%d%d",&x,&y,&n,&k);i--+n;scanf("%d%d%d",&a,&b,&c)) for(p=x;p>=a;p--)for(q=y;q>=b;q--)d[p][q]>=(t=d[p-a][q-b]+c)?d[p][q]=i?t:(p+q)*k:0; // for(p=x;p>=a;p--)for(q=y;q>=b;q--)!i|d[p][q]>(k=d[p-a][q-b]+c)?d[p][q]=i?k:(p+q)*k:0; // こうするとtが要らなくなるが2B伸びるので±0 printf("%d",d[x][y]); }
210B