uva--242(邮资问题 dp）-白红宇

uva--242(邮资问题 dp）

阅读量：5309 次

发布时间：2019-06-14

本文共 1025 字，大约阅读时间需要 3 分钟。

输入输出：

524 1 4 12 214 1 5 12 281025 1 7 16 31 885 1 15 52 67 99623 1 5 84 1 5 7 80

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

题意：

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

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

代码：

#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #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
            
              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
             
               &a ,const vector
              
                &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]
               
                ans) { ans=tmp; pos=i; } } printf("max coverage =%4d :",ans); for(int i=0; i