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;
}