我觉得黄学长刷的背包应该不会太水吧？！
选择第二个政党和第四个
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1e5+10,INF=1e6;
int n,a[310],tot;
int f[maxn];
int aa;char cc;
int read() {
aa=0;cc=getchar();
while(cc<‘0‘||cc>‘9‘) cc=getchar();
while(cc>=‘0‘&&cc<=‘9‘) aa=aa*10+cc-‘0‘,cc=getchar();
return aa;
}
bool cmp(const int x,const int y) {return x>y;}
int main() {
n=read();
for(int i=1;i<=n;++i)a[i]=read(),tot+=a[i];
sort(a+1,a+n+1,cmp);
memset(f,-1,sizeof(f));
f[0]=INF;tot/=2;
for(int i=1;i<=n;++i) {
for(int j=tot;j>=0;--j) if(f[j]!=-1) f[j+a[i]]=max(f[j+a[i]],min(f[j],a[i]));
}
for(int i=tot*2+1;i>tot;--i) if(i-f[i]<=tot) {
printf("%d",i);
return 0;
}
return 0;
}
windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。
输入文件paint.in第一行包含三个整数，N M T。 接下来有N行，每行一个长度为M的字符串，‘0‘表示红色，‘1‘表示蓝色。
输出文件paint.out包含一个整数，最多能正确粉刷的格子数。
30%的数据，满足 1 <= N,M <= 10 ； 0 <= T <= 100 。 100%的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。
竟然是SCOI的题。。。
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=50+5;
int n,m,tot,cl[maxn],dp[maxn*maxn],f[maxn][maxn];
int main() {
scanf("%d%d%d",&n,&m,&tot); int x;
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) scanf("%1d",&cl[j]),cl[j]+=cl[j-1];
memset(f,0,sizeof(f));
for(int j=1;j<=m;++j) for(int k=1;k<=j;++k) {
x=cl[j]-cl[k-1];x=max(x,j-k+1-x);
for(int t=1;t<=min(m,tot);++t) f[j][t]=max(f[j][t],f[k-1][t-1]+x);
}
for(int j=tot;j;--j) for(int k=1;k<=min(m,tot)&&k<=j;++k) dp[j]=max(dp[j],dp[j-k]+f[m][k]);
}
printf("%d",dp[tot]);
return 0;
}
一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。
音量用一个整数描述。输入文件中给定整数beginLevel，代表吉他刚开始的音量，以及整数maxLevel，代表吉他的最大音量。音量不能小于0也不能大于maxLevel。输入文件中还给定了n个整数c1,c2,c3…..cn，表示在第i首歌开始之前吉他手想要改变的音量是多少。
吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。
第一行依次为三个整数：n, beginLevel, maxlevel。
第二行依次为n个整数：c1,c2,c3…..cn。
输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于0或者高于maxLevel，输出-1。
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=50+5,maxnum=1000+10;
int n,x,d;
bool f[maxn][maxnum];
int aa,ff;char cc;
int read() {
aa=0;cc=getchar();ff=1;
while(cc<‘0‘||cc>‘9‘) {
if(cc==‘-‘) ff=-1;
cc=getchar();
}
while(cc>=‘0‘&&cc<=‘9‘) aa=aa*10+cc-‘0‘,cc=getchar();
return aa*ff;
}
int main() {
n=read();x=read();d=read();
f[0][x]=1;
for(int i=1;i<=n;++i) {
x=read();
for(int j=0;j<=d;++j) if(f[i-1][j]) {
if(j+x<=d) f[i][j+x]=1;
if(j-x>=0) f[i][j-x]=1;
}
}
for(int j=d;j>=0;--j) if(f[n][j]) {
printf("%d",j);return 0;
}
printf("-1");
return 0;
}
4 2
1 2
2 3
4 1
6 2
2
10
解释：挑出的是第二颗和第三颗糖。
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=200+10,maxm=20+5;
int n,m,a[maxn],b[maxn],dp[maxn][maxm][2*maxn];
int aa,ff;char cc;
int read() {
aa=0;cc=getchar();ff=1;
while(cc<‘0‘||cc>‘9‘) {
if(cc==‘-‘) ff=-1;
cc=getchar();
}
while(cc>=‘0‘&&cc<=‘9‘) aa=aa*10+cc-‘0‘,cc=getchar();
return aa*ff;
}
int main() {
n=read();m=read(); memset(dp,-1,sizeof(dp));dp[0][0][200]=0;
for(int i=1;i<=n;++i) a[i]=read(),b[i]=read();
for(int i=1;i<=n;++i) for(int j=0;j<=m;++j) for(int k=0;k<=400;++k) {
if(j&&dp[i-1][j-1][k]!=-1)
dp[i][j][k+a[i]-b[i]]=max(dp[i][j][k+a[i]-b[i]],dp[i-1][j-1][k]+a[i]+b[i]);
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
}
for(int i=0;i<=200;++i) if(dp[n][m][200-i]!=-1||dp[n][m][200+i]!=-1) {
printf("%d\n%d",i,max(dp[n][m][200-i],dp[n][m][200+i]));
return 0;
}
return 0;
}
/*
4 2
1 2
2 3
4 1
6 2
*/
原文：http://www.cnblogs.com/Serene-shixinyi/p/7624555.html