习题9-5 UVA 242

Stamps and Enovelope Size

题意：

给你最多贴S张邮票。有N个邮票集合，每个集合有不同的面值。问哪个集合的最大连续邮资最大，输出最大连续邮资和集合元素。

如果不止一个集合结果相同，输出集合元素少的，如果仍相同，输出最大面值小的。

思路：

最开始直接进行的深搜，感觉应该会TL，就放弃了。主要是莫有想到记忆化搜索的使用 - -， 果然太年轻。

用dp[i][j]表示使用了j个邮票后还差i，。
记忆化搜索找出最大的可能，如果有相同的则进行比较

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn = 1005;
int tp[15][15];
int a[15];
int n,num;
int dp[maxn][12];

int fin(int c,int cur,int sum)
{
    if(sum > num)
        return dp[cur][sum] = 0;
    if(dp[cur][sum] != -1)
        return dp[cur][sum];

    if(sum == num && cur != 0)
        return dp[cur][sum] = 0;
    if(cur == 0)
        return dp[cur][sum] = 1;
    for(int i = 1; i <= tp[c][0]; i++)
    {
        if(cur < tp[c][i])
            continue;
        dp[cur][sum] = fin(c,cur-tp[c][i],sum+1);
        if(dp[cur][sum] == 1)
            return 1;
    }
    return dp[cur][sum];
}

int get_(int a,int b)
{
    if(tp[a][0]<tp[b][0])return a;                  //比长度
    if(tp[b][0]<tp[a][0])return b;
    for(int i=tp[a][0]; i>0; i--)
    {
        if(tp[a][i]<tp[b][i])return a;              //比最大值
        if(tp[b][i]<tp[a][i])return b;
    }
    return a;
}

int main()
{
    while(scanf("%d",&num)!= EOF && num)
    {
        scanf("%d",&n);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&tp[i][0]);
            for(int j = 1; j <= tp[i][0]; j++)
            {
                scanf("%d",&tp[i][j]);
            }
        }


        int tans = -1;
        int ans = -1;
        for(int i = 1; i <= n; i++)
        {
            int tt = 0;
            int t = 0;
            memset(dp,-1,sizeof(dp));
            for(int j = 1;; j++)
            {
                if(fin(i,j,0))
                {
                    tt = j;
                    t = i;
                }
                else
                    break;
            }
            if(ans < tt)
            {
                ans = tt;
                tans = t;
            }
            else if(ans == tt)
            {
                tans = get_(t,tans);
            }
        }
        printf("max coverage =%4d :",ans);
        for(int i = 1; i <= tp[tans][0]; i++)
        {
            printf("%3d",tp[tans][i]);
        }
        printf("
");
    }
}