#include#include

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

1244. Gentlemen

系統(tǒng) 1650 0

http://acm.timus.ru/problem.aspx?space=1&num=1244

背包題? 理解并不難

主要在于如果答案有多個(gè)要輸出 -1

一個(gè)答案的話要輸出結(jié)果?? 否則輸出 0

用 sum [ n ] 表示到 n 有幾條路徑

狀態(tài)轉(zhuǎn)移方程為?

if(sum[j-a[i]])//a[i]表示第i個(gè)數(shù)據(jù)的大小

{
??????? sum[j]=max(sum[j]+1,sum[j-a[i]]);

}

代碼及其注釋:

      #include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>



#define LL long long



using namespace std;



const int N=100003;

int sum[N];//到 N 有幾條路徑

int f[N];// 記錄第一次到此用了那個(gè)數(shù)據(jù)

int a[103];// 數(shù)據(jù)大小

bool select[103];//是否用了

void Fselect(int x)//記錄用了哪幾個(gè)數(shù)據(jù)

{

    while(x)

    {

        select[f[x]]=true;

        x=x-a[f[x]];

    }

}

int main()

{

    //freopen("data.txt","r",stdin);

    int K,n;

    while(scanf("%d %d",&K,&n)!=EOF)

    {

        memset(sum,0,sizeof(sum));

        sum[0]=1;

        memset(select,false,sizeof(select));

        int m=0;

        for(int i=1;i<=n;++i)

        {

            scanf("%d",&a[i]);

            if(sum[K]>1)//如果答案有多個(gè) 則無(wú)需再找

            continue;

            m=min(m+a[i],K);//最大

            for(int j=m;j>=a[i];--j)

            {

                if(sum[j]==0)//如果是求得第一條到此路徑 記錄用了哪一數(shù)據(jù)

                {

                    f[j]=i;

                }

                if(sum[j-a[i]])//更新到此路徑數(shù)目

                {

                   sum[j]=max(sum[j]+1,sum[j-a[i]]);

                }

            }

            if(sum[K]==1)

            Fselect(K);

        }

        if(sum[K]==0)

        {printf("0\n");continue;}

        if(sum[K]>1)

        {printf("-1\n");continue;}

        for(int i=1;i<=n;++i)

        {

            if(!select[i])

            printf("%d ",i);

        }

        printf("\n");

    }

    return 0;

}


    

?

1244. Gentlemen


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號(hào)聯(lián)系: 360901061

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對(duì)您有幫助就好】

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 老师邪恶影院a啦啦啦影院 老师在办公室被躁到白浆 老湿机午夜影院 | 久久频这里精品99香蕉久网址 | 精品综合久久久久久97超人 | 日日狠狠的日日日日 | 亚洲视频手机在线 | 成年人视频在线免费 | www神马我不卡影院免费观看 | 免费中文字幕在线观看 | 久久久精品免费国产四虎 | 毛片a级| 亚洲91| 国产丶欧美丶日韩丶不卡影视 | 亚洲一区二区三区精品视频 | 精品国产一二三区在线影院 | 日日摸夜夜爽久久综合 | 国产精品分类视频分类一区 | 亚洲综合在线观看一区www | 午夜伦y4480影院中文字幕 | 特黄特级a级黄毛片免费观看多人 | 成人a毛片久久免费播放 | 91久久综合 | 夜夜天天干 | 久久精品资源站 | 精品久久久久久无码中文字幕 | 久久在线播放 | 欧美一级人与动毛片免费播放 | 国产精品爱久久久久久久三级 | 国产成人免费观看 | 日韩五月 | 国产亚洲自拍一区 | 99热在线观看精品 | 天天干天天干天天 | 亚洲高清毛片 | 久久99热精品 | 午夜手机看片 | 男女啪视频大全1000 | 四虎影院永久在线观看 | 中文字幕亚洲综合精品一区 | 国产uv1区二区三区 国产va | 天堂成人一区二区三区 | 久久澳门|