[abc] AtCoder Beginner Contest 204 A-F

前言

传送门 :

题意

给定 n n n个食物,每个食物有一个加热时间 a [ i ] a[i] a[i]

有两个微波炉,一个微波炉一次只能热一个食物,询问热完全部食物的最小时间

即 m i n ( ∑ A , ∑ B ) min(\sum A ,\sum B) min(∑A,∑B)

思路

将一个大集合 划分成两个小集合,使得两个小集合的属性最小

我们考虑使用动态规划

状体表示 : f [ i ] [ j ] f[i][j] f[i][j]前 i i i个食物是否可以花费 j j j分钟完成

状态转移 : f [ i ] [ j ] ∣ = f [ i ] [ j − 1 ] ( 不 选 第 i 个 物 品 − − 即 放 到 另 一 个 盘 子 中 f[i][j]|=f[i][j-1](不选第i个物品 -- 即放到另一个盘子中 f[i][j]∣=f[i][j−1](不选第i个物品−−即放到另一个盘子中 f [ i ] [ j + a [ i ] ] ∣ = f [ i ] [ j − 1 ] ( 选 第 i 个 物 品 f[i][j+a[i]]|=f[i][j-1]( 选第i个物品 f[i][j+a[i]]∣=f[i][j−1](选第i个物品

Code

const int N = 110,M = 1e5+10;
int a[N];
int f[N][M];//前i个物品 可以在J分钟内跑完
int sum,n;

void solve(){
	cin>>n;
	for(int i=1;i>a[i];
		sum+=a[i];
	}
	
	f[0][0] = 1;
	
	for(int i=1;i