学步园

用d[ i ][ j ]表示面额i可否用至多j张票表示； 状态转移很清晰不再详细说

#include <cstring>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
struct node{
vector<int> a;
bool operator < (const node& rhs) const{
      if(a.size() < rhs.a.size()) return true;
      else if(a.size() == rhs.a.size()){
         for(int i=0;i<a.size();i++){
           if(a[i]<rhs.a[i]) return 1;
           if(a[i]>rhs.a[i]) return 0;
           }
            return false;
      }
      return false;
}
}plan[100];
bool d[maxn][11],vis[maxn][11];
int s,n,MAX[maxn];
int dp(int i,int j,int k){
if(vis[i][j]) return d[i][j];
vis[i][j]=true;
if(i==0) { return d[i][j]=1;}
d[i][j]=false;
for(int g=0;g<plan[k].a.size();g++){
       int fee = plan[k].a[g];
       if(i>=fee&&j>0&&dp(i-fee,j-1,k)) d[i][j]=true;
}
return d[i][j];
}
int CMP(const int a,const int b){ //非类成员函数不得在括号末尾加 cv-qualifer 即 const 等
    return  a > b;
}
int main()
{
    while(scanf("%d",&s)&&s){
          scanf("%d",&n);
          for(int i=0;i<n;i++) plan[i].a.clear();
            for(int i=0;i<n;i++){
                int m;
                scanf("%d",&m);
                for(int j=0;j<m;j++){
                      int x;
                      scanf("%d",&x);
                      plan[i].a.push_back(x);
                }
                sort(plan[i].a.begin(),plan[i].a.end(),CMP);
            }
          sort(plan,plan+n);
          int max_=0,posi=0;
          for(int i=0;i<n;i++){
               MAX[i]=0;
               memset(vis,false,sizeof(vis));
               for(int j=1;;j++){
                    if(!dp(j,s,i)) {MAX[i]=j-1; break;}
               }
               if(max_ < MAX[i]) {
                   max_ = MAX[i]; posi = i;
               }
          }
          printf("max coverage =%4d :",max_);
          for(int i=plan[posi].a.size()-1;i>=0;i--){
               printf("%3d",plan[posi].a[i]);
          }
          printf("\n");
    }
    return 0;
}