碼迷,www.tparu.icu
吉利平特名人堂 > 其他好文 > 詳細

开平特色:多重部分和問題

時間:2019-05-23 18:25:40      閱讀:12      評論:0      收藏:0      [點我收藏+]

吉利平特名人堂 www.tparu.icu 標簽:back   --   bit   alt   src   pen   efi   name   個數   

  題意:有n種不同大小的數字ai 每種各mi個 判斷是否可以從這些數字之中選出若干個使它們的和恰好為K

 

樸素做法  為三次方

有一種 nK的做法:

dp[i][j]表示 前i個數  湊到j最多剩下多少個mi

 

dp[i][j]

1.如果dp[i][j]>=0 那么肯定為mi

2.如果 j<ai or  dp[i][j-ai]]<=0 那么為-1  表示無解

3. 其他情況  dp[i][j-ai]]-1;

技術圖片
#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=100+5;
int n,m,dp[N];
int a[N],m[N],K;
int main()
{
    RI(n,K);
    rep(i,1,n)RI(a[i]);
    rep(i,1,n)RI(m[i]);
    
    CLR(dp,-1);
    dp[0]=0;
    rep(i,1,n)
    rep(j,0,K)
    if(dp[j]>=0){dp[j]=m[i];}
    else if(j<a[i]||dp[j-a[i]]<=0){dp[j]=-1;}
    dp[j]=dp[j-a[i]]-1;
    
    if(dp[K]>=0)printf("Yes\n");
    else printf("No\n");
    
    return 0;
}
View Code

 

多重部分和問題

標簽:back   --   bit   alt   src   pen   efi   name   個數   

原文地址:https://www.cnblogs.com/bxd123/p/10913559.html

(0)
(0)
   
舉報
評論 一句話評論(0
0條  
登錄后才能評論!
? 2014 吉利平特名人堂 版權所有 京ICP備13008772號-2
迷上了代碼!
色子单双玩法 每天计划 赌场大小的玩法介绍 幸运28模式组合 幸运飞艇双单规律 重庆时时大小单双计划 下载牛牛游戏 百人游app 捕鱼达人2最老版本 抢庄牛牛技巧提前看牌 免费单机二人麻将 全天赛车pk10免费计划 pk10看走势图教程 北京pk10正规官方网站 彩票助赢计划软件是不是在维护 三年无错36码特围