暑假集训D2 2023.7.25 补题

D.P1796 汤姆斯的天堂梦

这道题目非常ex，赛时死活调不出来，思路是对的,容易发现是一个DAG,所以直接DP就好,虽然后面看题解AC了，发现是重边的问题。但还是来记录一下这道ex的题目，警醒一下自己切记注意重边！！
如下两份代码，一份爆0，一份AC

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e5+10;
int dp[110][110];
int n,k[110];
int g[110][110][110];

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	memset(dp,0x3f,sizeof dp);
	memset(g,0x3f,sizeof g);
	
	k[0] =1;
	dp[0][1]  =0;
	for(int i =1;i<=n;i++)
	{
		cin>>k[i];
		for(int j =1;j<=k[i];j++)
		{
			int x,cost;
			while(cin>>x&&x)
			{
				cin>>cost;
				g[i-1][x][j] = cost;
				
			}
		}
	}
	
	
	for(int dep= 1;dep<=n;dep++)
	{
		for(int i =1;i<=k[dep];i++)
		{
			for(int j =1;j<=k[dep-1];j++)
			{
				dp[dep][i] = min(dp[dep][i],dp[dep-1][j]+g[dep-1][j][i]);
				//cout<<dep<<":"<<j<<" "<<i<<" "<<dp[dep][i]<<endl;
			}
			
		}
	}
	int res = 2147483647;
	for(int i =1;i<=k[n];i++)
	{
		res = min(res,dp[n][i]);
	}
	cout<<res;
	return 0;
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e5+10;
int dp[110][110];
int n,k[110];
int g[110][110][110];

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	memset(dp,0x3f,sizeof dp);
	memset(g,0x3f,sizeof g);
	
	k[0] =1;
	dp[0][1]  =0;
	for(int dep =1;dep<=n;dep++)//星球等级
	{
		cin>>k[dep];
		for(int i =1;i<=k[dep];i++)//终点
		{
			int j,cost;//j为起点，cost为从j到i的花费
			while(cin>>j&&j)
			{
				cin>>cost;
				g[dep-1][j][i] = cost;
				
				dp[dep][i] = min(dp[dep][i],dp[dep-1][j]+g[dep-1][j][i]);
			}
		}
	}
	
	int res = 2147483647;
	for(int i =1;i<=k[n];i++)
	{
		res = min(res,dp[n][i]);
	}
	cout<<res;
	return 0;
}

只需要输入时取g[i-1][x][j] = min(g[i-1][x][j],cost);

L. P2663 越越的组队

看了半天题目毫无头绪.遂看题解

此题为背包变形题目,每个同学只能选1次,跟01背包非常类似.容量上限就是\(sum/2\).01背包一维是记录前i个人,一维记录当前的分数.但是加了一个限制:必须选择恰好一半的同学.
因此加一维记录一下选的人数就好了.
dp[i][j][k]表示前i个人中选j个总分是否能达到k
朴素背包代码如下

for(int i=1;i<=n;i++)
{
	dp[i][0][0] =1;
	for(int j = 1;j<=i;j++)
	{
		for(int k = 0;k<=5000;k++)
		{
			dp[i][j][k] = dp[i-1][j][k];
			if(!dp[i][j][k]&&k>=a[i])
			{
				dp[i][j][k] = dp[i-1][j-1][k-a[i]];
			}
		}
	}
}

可以对第一层进行压缩.不再赘述
完整代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define endl '\n'
using namespace std;
const int N = 1e5+10;
int dp[110][10010];
int n;
int a[N];
int sum = 0;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	dp[0][0] =1;
	for(int i=1;i<=n;i++)
	{
		for(int j = i;j>=1;j--)
		{
			for(int k = 5000;k>=0;k--)
			{
				//dp[i][j][k] = dp[i-1][j][k];
				if(!dp[j][k]&&k>=a[i])
				{
					dp[j][k] = dp[j-1][k-a[i]];
				}
			}
		}
	}
	int res = 0;
	for(int i =0;i<=sum/2;i++)
	{
		if(dp[n/2][i])
		{
			res = i;
		}
	}
	cout<<res;
	return 0;
}