A1269 庆功会

# include<iostream>
using namespace std;

const int N=505,M=6005;//奖品种数，拨款金额 
int n,m,v,w,s,p;
int dp[M];

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>v>>w>>s;
		p=1;
		while(s>p){
			s-=p;
			for(int j=m;j>=v;--j)
				dp[j]=max(dp[j],dp[j-v*p]+w*p);
		}
		for(int j=m;j>=v;--j)
			dp[j]=max(dp[j],dp[j-v*s]+w*s);
	}
	cout<<dp[m];
	return 0;
}

A1270 混合背包

# include<iostream>
using namespace std;

const int N=35,M=205;//物品数量，背包容量 
int n,m,w,c,p,k;
int dp[M];

int main(){
	cin>>m>>n;
	for(int i=1;i<=n;++i){
		cin>>w>>c>>p;
		k=1;
		if(p==0)
			for(int j=w;j<=m;++j)
				dp[j]=max(dp[j],dp[j-w]+c);
		else{
			while(p>k){
				p-=k;
				for(int j=m;j>=w;--j)
					dp[j]=max(dp[j],dp[j-w*k]+c*k);
			}
			for(int j=m;j>=w;--j)
				dp[j]=max(dp[j],dp[j-w*p]+c*p);
		}
	}
	cout<<dp[m];
	return 0;
}

A1271 潜水员

# include<iostream>
using namespace std;

const int M=25,N=85,K=1005;//氧，氮，背包容量 
int m,n,k,a,b,c;
int dp[M*K][N*K];

int main(){
	cin>>m>>n>>k;
	for(int i=1;i<=k;++i){
		cin>>a>>b>>c;
		for(int j=m*k;j>=a;--j)
			for(int l=n*k;k>=b;--l)
				dp[j][l]=min(dp[j][l],dp[j-a][j-b]+c);
	}
	cout<<dp[m];
	return 0;
}

#include<cstdio>
#include<cstring>  
using namespace std;
int v, u, k;
int a[1001], b[1001], c[1001];
int f[101][101];

int main(){
    memset(f,127,sizeof(f));   
    f[0][0] = 0;
    scanf("%d%d%d",&v,&u,&k);
    for (int i = 1; i <= k; i++)
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
    for (int i = 1; i <= k; i++)
      for (int j = v; j >= 0; j--)
        for (int l = u; l >= 0; l--)
        {
           int t1 = j+ a[i],t2 = l + b[i];
           if (t1 > v)  t1 = v;  //若氮、氧含量超过需求，可直接用需求量代换，
           if (t2> u)  t2 = u; //不影响最优解
           if (f[t1][t2] > f[j][l] + c[i])  f[t1][t2] = f[j][l] + c[i];
        }
    printf("%d",f[v][u]);
    return 0;
  }

A1272 分组背包

# include<iostream>
using namespace std;

const int N=35;
int v,n,t,dp[205];
int w[N],c[N],f,p[12][N],cnt[12];

int main(){
	cin>>v>>n>>t;
	for(int i=1;i<=n;++i){
		cin>>w[i]>>c[i]>>f;
		p[f][++cnt[f]]=i;
	}
	for(int i=1;i<=t;++i)
		for(int j=v;j>=0;--j)
			for(int k=1;k<=cnt[i];++k){
				int l=p[i][k];
				if(j>=w[l]) dp[j]=max(dp[j],dp[j-w[l]]+c[l]);
			}
	cout<<dp[v];
	return 0;
}

P1282 多米诺骨牌

# include<iostream>
# include<cstring>
using namespace std;

const int N=1005,mid=5010;
int n,a[N],b[N],s1,s2,t,k,l;
int dp[10100];

int main(){
	cin>>n;
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;++i){
		cin>>a[i]>>b[i];
		s1+=a[i],s2+=b[i];
	}
	dp[s1-s2+mid]=0;
	for(int i=1;i<=n;++i){
		t=a[i]-b[i];
		if(t<0)
			for(int j=5000;j>=2*t-5000;--j){
				k=mid+j;
				dp[k]=min(dp[k],dp[k+2*t]+1);
			}
		if(t>0)
			for(int j=-5000;j<=5000-2*t;++j){
				k=mid+j;
				dp[k]=min(dp[k],dp[k+2*t]+1);
			}
	}
	for(int i=0;i<=5000;++i){
		k=dp[mid+i],l=dp[mid-i];
		if(k>N&&l>N) continue;
		else{
			cout<<min(k,l);
			break;
		}
	}
	return 0;
}

P1284 三角形牧场

# include<iostream>
# include<cmath>
using namespace std;

const int N=45,M=805;
int n,l[N],s;
double p,ans=-1;
bool f[M][M];

int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>l[i];
		s+=l[i];
	}
	p=s/2.0;
	f[0][0]=1;
	for(int i=1;i<=n;++i)
		for(int j=p;j>=0;--j)
			for(int k=p;k>=0;--k){
				if(j>=l[i]) f[j][k]=f[j][k]||f[j-l[i]][k];
				if(k>=l[i]) f[j][k]=f[j][k]||f[j][k-l[i]];
			}
	for(int i=1;i<p;++i)
		for(int j=1;j<p;++j){
			int k=s-i-j;
			if(!f[i][j]) continue;
			if(i+j>k&&i+k>j&&j+k>i)
				ans=max(ans,(p-i)*(p-j)*(p-k));
		}
	if(ans==-1) cout<<ans;
	else cout<<(int)(sqrt(p*ans)*100);
	return 0;
}