今天是我们第二天集训，我来说一下题目的思路和怎么做：
第一题：
//题目必须在八十看
第一题一看就是比较简单的背包，同VijosNASA的食物计划，直接打模板，我就不说什么了，我这里用了滚动数组，不会背包可以直接在网上找，直接粘提解：
#include <bits/stdc++.h> using namespace std; int a[1001],b[1001],c[1001],f[1001][1001]; int main() { memset(f,0,sizeof(f)); int i,j,k,l,n,m; cin>>m>>k; cin>>n; for(i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]; for(i=1;i<=n;i++) { for(j=m;j>=0;j--) { for(l=k;l>=0;l--) { if(j>=a[i]&&l>=b[i]) f[j][l]=max(f[j][l],f[j-a[i]][l-b[i]]+c[i]); } } } cout<<f[m][k]<<endl; return 0; }第二题：
//题目
第二题就是用字典序做，先把相同的放一块，如果满足条件就一个一个找，直到找到头或者不同了，筛选出来后再进行排序即可做出：
#include <bits/stdc++.h> using namespace std; int i,j,k,l,n,m,sum=0; struct hh { char s[32]; }cha[100005]; bool cmp(hh a,hh b) { return strcmp(a.s,b.s)<0; } struct q { int tot; int pos; }a[100005]; bool cmp1(q a,q b) { if(a.tot!=b.tot) return a.tot>b.tot; return a.pos<b.pos; } void init() { cin>>n; for(i=1;i<=n;++i) cin>>cha[i].s; sort(cha+1,cha+n+1,cmp); for(i=1;i<=n;++i) { if(strcmp(cha[i].s,cha[i+2].s)==0) { sum++; a[sum].pos=i; a[sum].tot=3; for(j=i+3;j<=n;++j) { if(strcmp(cha[i].s,cha[j].s) != 0) { i=j-1; break; } a[sum].tot++; if(j==n) return ; } } } } void work() { printf("%d\n",sum); sort(a+1,a+sum+1,cmp1); for(i=1;i<=n;++i) cout<<cha[a[i].pos].s<<endl; } int main() { init(); work(); return 0; }第三题：第三题本蒟蒻还没有AC，不敢给大家讲，十号AC了在放到上面
第四题：
//题目
第四题乍一看是一道非常简单的01背包，可当我们看到m的范围就发现事情并没有那么简单，但是m<=10000用01背包是肯定没有问题的，然后当m太大的时候我们就可以搜索＋剪枝了，sumw[i]以及sumv[i]代表的是从i到k的和，在搜索前先对数组进行排序，后面消耗的大，我再说一下剪枝的方法：如果当前价值加上后面所有的价值小于现在最大价值我们就可以return了，如果后面所有的质量和当前质量加起来都没有限制的质量高的话，判断加上后面所有的大不大于max，然后return，就这么多，好像也没什么了~
#include <bits/stdc++.h> using namespace std; #define ll long long #define maxn 100001 ll sumw[maxn],sumv[maxn],f[maxn]; ll i,j,k,l,n,m; ll Max=-1; struct hh { ll w,v; }a[1001]; bool cmp(hh a,hh b) { return a.w>b.w; } void init() { cin>>n>>m;k=1; for(i=1;i<=n;++i) { ll x,y; cin>>x>>y; if(x>m) continue; a[k].w=x; a[k++].v=y; } } void dfs(ll i,ll x,ll y) { if(i==k-1) { if(y>Max) Max=y; return ; } if(x+sumw[i]<=m) { dfs(k-1,x+sumw[i],y+sumv[i]); return; } if(y+sumv[i]<Max) return; if(x+a[i].w<=m) dfs(i+1,x+a[i].w,y+a[i].v); dfs(i+1,x,y); } void work() { sort(a+1,a+k+1,cmp); sumw[k]=sumv[k]=0; for(i=k;i>0;--i) sumw[i]=sumw[i+1]+a[i].w,sumv[i]=sumv[i+1]+a[i].v; dfs(1,0,0); } int main() { init(); if(m<=10000){ memset(f,0,sizeof(f)); for(ll i=1;i<k;i++){ for(ll j=m;j>=a[i].w;j--){ f[j]=max(f[j],f[j-a[i].w]+a[i].v); } } cout<<f[m]<<endl; return 0; } work(); cout<<Max<<endl; return 0; } /* 3 10 1 3 5 8 8 10 */ ~~~谢谢观看~~~
