読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


POJ 1276 Cash Machine

問題文

DP強化週間。
目標金額と使用できる硬貨の単位とその枚数が与えられ、目標の金額を超えずになるべく近く払おうとするときその金額を答える問題。

1742 Coins に酷似している。
dp[i]:=(金額iを払おうとするときに余るコインの枚数)でDP。アリ本に同じ問題があってそれを参考にした。

int dp[100001];
int Dk[11], Nk[11];

int main(int argc, char **argv){
  int cash;
  while(cin >> cash){
    //入力
    int n; cin >> n;
    for(int i = 0; i < n; i++) cin >> Nk[i] >> Dk[i];

    //DP
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for(int i = 0; i < n; i++){
      for(int j = 0; j <= cash; j++){
	if(dp[j] >= 0){
	  dp[j] = Nk[i];
	}else if(j < Dk[i] || dp[j - Dk[i]] <= 0){
	  dp[j] = -1;
	}else{
	  dp[j] = dp[j - Dk[i]] - 1;
	}
      }
    }

    //出力
    int ans;
    for(ans = cash; ans >= 0; ans--){
      if(dp[ans] >= 0) break;
    }
    cout << ans << endl;
  }
  return 0;
}

この解き方で良いとすぐに気づいたまではよかったけどDPの中身が詰めきれなかった。典型問題っぽいので覚えておきたい。今見るととてもシンプルに思えるし。

あとソースコメントもほんとに簡単なもの位はつけようと思う。

しょげないでよBaby 眠れば治る