酷暑一夏1

不忘初心，方得始终

• 于  01背包, Vijos, 问题集合  阅读 

Vijos 基础01背包问题 1133 装箱问题,1104 采药,1025 小飞侠的游园方案 题解

题目

略

题解

直接套模版。
装箱问题需要输出$V-dp[n][V]$，其它输出$dp[n][V]$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//1025
#include<cstdio>
#include<algorithm>
const int MAXN=100+5;
const int MAXV=1000+5;
int dp[MAXN][MAXV];
int main()
{
	int n,v,c,w;
	scanf("%d",&n);
	scanf("%d",&v);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&w,&c);
		for(int j=1;j<=v;j++)
			if(j>=c) dp[i][j]=std::max(dp[i-1][j],dp[i-1][j-c]+w); else dp[i][j]=dp[i-1][j];
	}
	printf("%d",dp[n][v]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//1104
#include<cstdio>
#include<algorithm>
const int MAXN=100+5;
const int MAXV=1000+5;
int dp[MAXN][MAXV];
int main()
{
	int n,v,c,w;
	scanf("%d %d",&v,&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&c,&w);
		for(int j=1;j<=v;j++)
			if(j>=c) dp[i][j]=std::max(dp[i-1][j],dp[i-1][j-c]+w); else dp[i][j]=dp[i-1][j];
	}
	printf("%d",dp[n][v]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//1133
#include<cstdio>
#include<algorithm>
const int MAXN=30+5;
const int MAXM=20000+5;
int n,v,c,dp[MAXN][MAXM];
int main()
{
	scanf("%d",&v);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c);
		for(int j=1;j<=v;j++)
			if(j>=c) dp[i][j]=std::max(dp[i-1][j],dp[i-1][j-c]+c); else dp[i][j]=dp[i-1][j];
	}
	printf("%d",v-dp[n][v]);
	return 0;
}
最近的文章

Vijos1411 Dejected Birthday-允诺 题解

题目9.19是青子的生日…而在那日晚,基德发出了盗窃”忧郁的生日”的预告函.快斗在两难的抉择下,最终决定:以最快速度将”忧郁的生日”收入囊中,再赶去为青子表演魔术–这是他对青子的允诺.“忧郁的生日”被保存在一个深不可测的大楼里.而从大门到最里面的房间有无数条路径.整个大楼可以被看做一个巨大的无向图, …

• 于  Vijos 继续阅读
更早的文章

Vijos1248 最厉害的机器人 题解

题目机器人们都想知道谁是最厉害的，于是它们进行如下一种比赛。每个机器人需要在最短的时间内找到自己面前的一个球，走到它面前并绕过它，将球推进身后的球门。首先Wind给了每个机器人一些钱，让他们去补充自己的装备，Wind给的钱恰好够补充k个装备。有如下几个装备可供补充：亮度传感器，超声波测距，触动传感器 …

• 于  Vijos, Wind~机器人系列 继续阅读