PKU : 3456 - Frobenius

PKU 動的計画法

問題概要

http://poj.org/problem?id=3456

「a⋅w + b⋅x + c⋅y + d⋅z」という式のa〜dが入力として与えられる.(a〜dは0以上の整数)
w,x,y,zに, 0以上の整数を代入できるとき, この式を使って作ることができない100万以下の整数の数を答えよ.
また, 作ることができない数の最大値を答えよ. 最大値が100万を超える場合は-1と出力すること.

アルゴリズム

bool dp[MAX]としたとき,

  • dp[0] = true
  • dp[i] = dp[i-a] || dp[i-b] || dp[i-c] || dp[i-d]

という漸化式でDPができる.

反省

bool dp[4][MAX], t[1]=a,t[2]=b,t[3]=c,t[4]=dとして,

  • dp[0][0] = true
  • dp[i][j] = dp[i-1][j] || dp[i][j-t[i] ]

でできると思ったけど, TLEした.
これは, dp[MAX]のときの解法を, 無駄にオーダをかけて解いてるだけ.
無駄すぎる処理.

プログラム

int dp[2000002];

int main(void){
  int T;
  int a,b,c,d;

  cin>>T;

  while(T--){
    cin>>a>>b>>c>>d;
    memset(dp,0,sizeof(dp));
    dp[0] = 1;

    int cnt = 0;
    int last = -1;

    rep(i,1050001){
      cnt += (i <= 1000000 ? !dp[i] : 0);
      if(dp[i]) dp[i+a] = dp[i+b] = dp[i+c] = dp[i+d] = 1;
      else last = i;
    }

    cout<<cnt<<endl;
    cout<<(last > 1000000 ? -1 : last)<<endl;
  }
}