hdu1085 多重部分和问题

　　题目大意是给定1 2 5的数量 a, b, c, 问1 2 5不能组成的最小的数是多少？可以使用dp来解决， 定义dp[i][j]为前i种组成j的时候第i中数剩余多少， 那么

　　dp[i][j] = mi (dp[i-1][j]>=0)   -1 (a[i]>j || dp[i][j-a[i]]<=0)   dp[i][j-a[i]]-1 (其他), 代码如下：

　　

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int a[5] = {0, 1, 2, 5};
int m[5];
int dp[5][15000+10];    //前i中组成j的时候 第i种剩余多少

int main()
{
    while(cin>>m[1]>>m[2]>>m[3])
    {
        if(m[1]==0 && m[2]==0 && m[3]==0) break;
        memset(dp, -1, sizeof(dp));
        dp[0][0] = 0;
        for(int i=1; i<=3; i++)
            for(int j=0; j<=15000; j++)
            {
                if(dp[i-1][j] >= 0) dp[i][j] = m[i];
                else if(a[i]>j || dp[i][j-a[i]]<=0) dp[i][j] = -1;
                else dp[i][j] = dp[i][j-a[i]]-1;
            }
        int res;
        for(int j=0; j<=15000; j++)
            if(dp[3][j] == -1)
            {
                res = j;
                break;
            }
        cout<<res<<endl;
    }
    return 0;
}