POJ 1276 Cash Machine

個数制限付き部分和問題

完全に蟻ゲー

詳しくは蟻本p62参照

#include <algorithm>
#include <string.h>
#include <iostream>
#include <cstdio>

using namespace std;
int a[11];
int m[11];
int dp[100003];
int main(){
    int cash;
    while(cin >> cash){
        int n;
        scanf("%d",&n);
        for(int i = 0;i < n;i++){
            scanf("%d%d",&m[i],&a[i]);
        }   
        memset(dp,-1,sizeof(dp));
        int ans = 0;
        dp[0] = 0;
        for(int i = 0;i < n;i++){
            for(int j = 0;j <= cash;j++){
                if(dp[j] >= 0){ 
                    dp[j] = m[i];
                }else if(j < a[i] || dp[j-a[i]] <= 0){ 
                    dp[j] = -1; 
                }else{
                    dp[j] = dp[j-a[i]] - 1;
                }   
            if(dp[j] >= 0)ans = max(ans,j);
            }   
        }   
        printf("%d\n",ans);

    }   
    return 0;
}