必赢亚洲手机app下载


硬盘结构决定瓶颈

我会招什么样的成品经营

必赢亚洲手机app背包dp专题磨练

新春佳节佳话之打牌

描述

过年的时候,大人们最喜爱的移动,就是打牌了。xiaomengxian不会打牌,只可以坐在一边瞅着。

那天,正当一群人打牌打得起劲的时候,突然有人喊道:“那副牌少了几张!”大千世界一数,果然是少了。于是那副牌的持有者得意地说:“那是一幅特制的牌,我清楚整副牌每一张的轻重。只要我们称一下余下的牌的总重量,就能明了少了什么样牌了。”大家都以为那个法子不错,于是称出剩下的牌的总重量,伊始盘算少了怎么牌。由于数据量比较大,过了不久,我们都算得晕头转向了。

那儿,xiaomengxian大声说:“你们看我的吧!”于是她拿出笔记本电脑,编出了一个主次,很快就把缺乏的牌找了出去。

假设是你遇上了那般的意况吧?你能办到同样的作业吗?

格式

输入格式

先是行一个整数TotalW,表示剩下的牌的总重量。

第二行一个整数N(1<N<=100),表示那副牌有稍许张。

接下去N行,每行一个平头Wi(1<=Wi<=1000),表示每一张牌的轻重。

输出格式

比方无解,则输出“0”;即使有多解,则输出“-1”;否则,按照升序输出丢失的牌的编号,相邻七个数里面用一个空格隔开。

样例1

样例输入1

270
4
100
110
170
200

Copy

样例输出1

2 4

Copy

限制

依次测试点1s

提示

Sample
input #2
270
4
100
110
160
170

Sample
output #2
-1

Sample
input #3
270
4
100
120
160
180

Sample
output #3
0

题解

01背包判断方案数嘛,要求放个vis记录一下答案的号码

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 int V,n,w[105],f[100005],vis[100005],sum,cnt,ans[105];
 6 int main()
 7 {
 8     scanf("%d%d",&V,&n);
 9     for(int i=1 ; i<=n ; ++i )
10     {
11         scanf("%d",&w[i]);
12         sum+=w[i];
13     }
14     V=sum-V;
15     f[0]=1;
16     for(int i=1 ; i<=n ; ++i )
17         for(int j=V ; j>=w[i] ; --j)
18         {
19         
20             if(f[j-w[i]])
21             {
22                 if(!f[j])vis[j]=i;
23                 f[j]+=f[j-w[i]];
24             }
25         }
26     if(!f[V])printf("0");
27     else if(f[V]>1)printf("-1");
28     else if(f[V]==1)
29     {
30         for(int i=V ; i>0 ; i-=w[vis[i]])ans[++cnt]=vis[i];
31         sort(ans+1,ans+1+cnt); 
32         for(int i=1 ; i<=cnt ; ++i )printf("%d ",ans[i]);
33     }
34     return 0;
35 }

搭建双塔

描述

2001年七月11日,一场突发的劫数将伦敦世界贸易中央大厦夷为平地,Mr.
F曾目睹了这一次魔难。为了纪念“9?11”事件,Mr.
F决定自己用水晶来搭建一座双塔。

Mr.
F有N块水晶,每块水晶有一个惊人,他想用那N块水晶搭建两座有同一中度的塔,使她们变成一座双塔,Mr.
F可以从那N块水晶中任取M(1≤M≤N)块来搭建。然而他不清楚能不能使两座塔有同等的冲天,也不知情如若能搭建成一座双塔,那座双塔的最大中度是稍微。所以她来请您扶助。

加以水晶的数量N(1≤N≤100)和每块水晶的惊人Hi(N块水晶中度的总和不当先2000),你的职务是判断Mr.
F能如故不能用那个水晶搭建成一座双塔(两座塔有同一的万丈),假诺能,则输出所能搭建的双塔的最大中度,否则输出“Impossible”。

格式

输入格式

输入的首先行事一个数N,表示水晶的多寡。第二表现N个数,第i个数表示第i个水晶的惊人。

输出格式

出口仅包涵一行,若是能搭成一座双塔,则输出双塔的最大惊人,否则输出一个字符串“Impossible”。

样例1

必赢亚洲手机app,样例输入1

5
1 3 4 5 2

样例输出1

7
题解
比较好的一道dp,设f[i][j]表示前i个水晶搭的两座塔相差高度为j时较低塔的高度
四种情况可以转移
该水晶搭给矮塔后仍然是矮塔 搭给高塔 搭给矮塔后变成高塔 不选该水晶
然后转移就行了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #include<cstring>
 6 using namespace std;
 7 int N;
 8 int a[300],sum[300];
 9 int f[300][2500];
10 int main(){
11     memset(f,-0x7f,sizeof(f));
12     cin>>N;
13     for(int i=1;i<=N;i++)cin>>a[i];
14     sort(a+1,a+N+1);
15     for(int i=1;i<=N;i++) sum[i]=sum[i-1]+a[i];
16     f[1][0]=0;f[1][a[1]]=0;
17     for(int i=2;i<=N;i++){
18         for(int j=0;j<=sum[i];j++){
19         int h1=j-a[i];
20         if(h1>=0&&h1<=sum[i-1]) 
21         f[i][j]=max(f[i][j],f[i-1][h1]);
22         int h2=j+a[i];
23         if(h2<=sum[i-1]) 
24         f[i][j]=max(f[i][j],f[i-1][h2]+a[i]);
25         int h3=a[i]-j;
26         if(h3>=0&&h3<=sum[i-1]) 
27         f[i][j]=max(f[i][j],f[i-1][h3]+h3);
28         int h4=j;
29         if(h4<=sum[i-1]) 
30         f[i][j]=max(f[i][j],f[i-1][j]);
31         }
32     }
33     if(f[N][0]<=0){
34     cout<<"Impossible";
35     return 0;
36     }
37     cout<<f[N][0];
38     return 0;
39 }

 

相关文章

No Comments, Be The First!
近期评论
    功能
    网站地图xml地图