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;
}