POJ 3456 Frobenius
問題
正の整数a,b,c,dに対するFrobenius数とは、w,x,y,z≧0に対してwa+xb+yc+zdとして表すことのできない最大の数である。
1000000以下の、wa+xb+yc+zdとして表せない数の個数および、Frebonius数を求めよ。
Frebonius数が1000000より大きい場合-1を出力せよ。
制約条件
a,b,c,d≦1000000
方針
愚直にDPする。
can[i]が1のときiがwa+xb+yc+zdとして表せるとすると、
can[i+a]とcan[i+b]とcan[i+c]とcan[i+d]はwa+xb+yc+zdとして表すことができる。
ソースコード
bool can[1100001]; int sum[1100001]; int main(){ int cs; scanf("%d",&cs); while(cs--){ memset(can,0,sizeof(can)); memset(sum,0,sizeof(sum)); int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); int ans=-1; can[0]=1; for(int i=0;i<=1050000;i++){ if(can[i])can[i+a]=can[i+b]=can[i+c]=can[i+d]=1; else ans=max(ans,i); sum[i]+=(i?sum[i-1]:0)+!can[i]; } printf("%d\n",sum[1000000]); printf("%d\n",ans>1000000?-1:ans); } return 0; }