uva-242(邮资有关问题 dp）

uva--242(邮资问题 dp）

输入输出：

Sample Input

5
2
4 1 4 12 21
4 1 5 12 28
10
2
5 1 7 16 31 88
5 1 15 52 67 99
6
2
3 1 5 8
4 1 5 7 8
0

Sample Output

max coverage =  71 :  1  4 12 21
max coverage = 409 :  1  7 16 31 88
max coverage =  48 :  1  5  7  8

题意：

    最多用S个邮票拼出最大连续数值，每组共有N组样例，每组第一个是数组元素个数，输出字典序最小的一组。

用二维的状态其实就可以了，i,j,k分别表示取到数组前i位用j个邮票是否能拼出k，感觉有点像背包，输入并不都是排好序的，需要排序。

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<cstring>
#include<vector>
#include<algorithm>
#define INF 0X3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;

typedef long long ll;
typedef unsigned long long llu;
const int maxd=10+5;
int n,s;
vector<int> st[maxd];
int dp[maxd][1005];

bool ok(int x)
{
        for(int j=0; j<=s; ++j)
            if(dp[j][x])
                return true;
    return false;
}

bool cmp(const vector<int> &a ,const vector<int> &b)
{
    int lena=a.size(),lenb=b.size();
    if(lena==lenb)
        for(int i=lena-1;i>=0;--i)
           if(a[i]!=b[i]) return a[i]<b[i];
    return lena<lenb;
}

int solve(int x)
{
    mem(dp,0);

    int len=st[x].size();
    int c=st[x][len-1]*s;

    for(int j=0; j<=s; ++j) dp[j][0]=1;
   // for(int i=0; i<=len; ++i) dp[i][0][0]=1;

    for(int i=1; i<=len; ++i)
    {
       // memcpy(dp[i],dp[i-1],sizeof(dp[i]));
        for(int j=1; j<=s; ++j)
        {
            int w=j*st[x][i-1];

            for(int m=j; m<=s; ++m)
                for(int k=w; k<=c; ++k)
                    if(dp[m-j][k-w])
                        dp[m][k]=1;
        }
    }

    int ans=0;
    for(int i=1; i<=c; ++i)
    {
        if(ok(i)) ans=i;
        else break;
    }

    return ans;

}

int main()
{
    freopen("1.txt","r",stdin);
    while(scanf("%d",&s)==1 && s)
    {
        scanf("%d",&n);
        for(int i=0; i<n; ++i)
        {
            int x,tmp;
            st[i].clear();
            scanf("%d",&x);
            for(int j=0; j<x; ++j)
                scanf("%d",&tmp),st[i].push_back(tmp);
            sort(st[i].begin(),st[i].end());
        }
        sort(st,st+n,cmp);

        int ans=0,pos=-1;
        for(int i=0; i<n; ++i)
        {
            int tmp=solve(i);
//            cout<<tmp<<endl;
            if(tmp>ans)
            {
                ans=tmp;
                pos=i;
            }
        }

        printf("max coverage =%4d :",ans);
        for(int i=0; i<st[pos].size(); ++i)
            printf("%3d",st[pos][i]);
        printf("\n");
    }
    return 0;
}