Stamps and Envelope Size-白红宇

Stamps and Envelope Size

阅读量：5320 次

发布时间：2019-06-14

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

题意：

容量为s的信封，给n组邮票的面值，求哪一组能组成的连续的面值的最大值最大，若有多组答案，输出面值数量最小的一组，若数量相等，输出最大面值最小的一组，若最大面值相等，输出第二大面值最小的一组，依次类推。

分析：

可以从小到大枚举面值直到不能组成，dp[i][j]是否能组成面值为i，用邮票数量为j dp[i][j]|=dp[i-v[k]][j-1],记忆化搜索即可

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;typedef pair
                      
                        PII;typedef long long ll;#define lson l,m,rt<<1#define pi acos(-1.0)#define rson m+1,r,rt<<11#define All 1,N,1#define read freopen("in.txt", "r", stdin)const ll INFll = 0x3f3f3f3f3f3f3f3fLL;const int INF= 0x7ffffff;const int mod = 1000000007;struct node{ int v1[15],len,d;}e[15];bool cmp(node x,node y){ if(x.d!=y.d)return x.d>y.d; else if(x.len!=y.len)return x.len
                       
                        =0;--k) if(x.v1[k]!=y.v1[k]) return x.v1[k]
                        
                         =val[id][i]&&dfs(v-val[id][i],num-1,id)) return dp[v][num]=1; } return dp[v][num]=0;}int main(){ while(~scanf("%d",&s)&&s){ scanf("%d",&n); for(int i=0;i

;

转载于:https://www.cnblogs.com/zsf123/p/4888469.html

你可能感兴趣的文章