DP入门

标签：const 入门 int d% Alice DP include dp

AT-abc286-d

传送门

题意简述

有 \(n\) 种纸币，其中对于第 \(i(1≤i≤n)\) 种纸币，它的面值是 \(a_i\)元，我们有 \(b_i\) 张这种纸币。

请求出在不找零的情况下，用这些纸币能否正好付 \(x\) 元，如果能则输出 \(Yes\)，不能则输出 \(No\)。

题目解析

类似多重背包，设 \(f[i][j]\) 代表使用前 \(i\) 种纸币，能否正好支付 \(j\) 元（布尔），那么答案即为 \(f[n][x]\)

循环枚举，\(i\) 种纸币，每种用了 \(j\) 张，当前支付 \(k\) 元。从前面 \(i-1\) 种纸币处转移过来，得出转移

\(f[i][k]=f[i-1][k-j*a[i]]\)

具体实现

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=55;
const int M=1e4+10;
int n,x;
int a[N],b[N];
int f[N][M];

int main(){
	scanf("%d%d",&n,&x);
	for(int i=1;i<=n;++i) scanf("%d%d",&a[i],&b[i]);
	f[0][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=b[i];++j){
			for(int k=0;k<=x;++k){
				if(a[i]*j>k) continue;
				if(f[i-1][k-a[i]*j]) f[i][k]=1;
			}
		}
	}
	if(f[n][x]) puts("Yes");
	else puts("No");
	return 0;
}

AT-dp-l

传送门

题意简述

有一个双端队列，双方轮流取数，只能从队头或队尾取数，取完数后将这个数从队列中弹出。双方都希望自己取的所有数之和尽量大，且双方都以最优策略行动，假设先手取的所有数之和为 \(X\)，后手取的所有数之和为 \(Y\)，求 \(X-Y\)

题目解析

经典套路。

设 \(f[i][j]\) 表示从队头取到 \(i\)，从队尾取到 \(j\) 时的 \(X-Y\)，那么答案是 \(f[1][n]\)

考虑子状态，\(f[i][j]\) 是从 \(f[i+1][j]\) 或 \(f[i][j-1]\) 转移而来的，\(Alice\) 对答案的贡献为正， \(Bob\) 对答案的贡献为负，则转移方程可得：

如果轮到 \(Alice\) 取数，那么 \(f[i][j]=max(f[i+1][j]+a[i],f[i][j-1]+a[j])\)

否则 \(Bob\) 取数，\(f[i][j]=min(f[i+1][j]-a[i],f[i][j-1]-a[j])\)

问题来了，如何判断到谁取数？

发现取到 \([i,j]\) 时，\(i\) 前面取了 \(i-1\) 个，\(j\) 后面取了 \(n-j\) 个，那么判断取数个数奇偶即可。偶数轮到 \(Alice\) ，奇数轮到 \(Bob\) 。

\(Tips:\) 注意初始状态 \(f[i][i]\) ，还有题目数据范围开 long long。

具体实现

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
const int N=3005;
int n;
ll f[N][N],a[N];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int len=1;len<=n;++len){
		for(int i=1;i<=n;++i){
			int j=i+len-1;
			if(i==j){
				if((i-1+n-j)&1) f[i][j]=-a[i];
				else f[i][j]=a[i];
			}
			if((i-1+n-j)&1) f[i][j]=min(f[i+1][j]-a[i],f[i][j-1]-a[j]);
			else f[i][j]=max(f[i+1][j]+a[i],f[i][j-1]+a[j]);
		}
	}
	printf("%lld\n",f[1][n]);
	return 0;
}

AT-tdpc-game

传送门

题意简述

\(Alice\) 和 \(Bob\) 在玩游戏。初始时有两座山，左边的山上有 \(A\) 个物品，从上到下的第 \(i\) 个价值为 \(a_i\)；右边的山上有 \(B\) 个物品，从上到下的第 \(i\) 个价值为 \(b_i\)。\(Alice\) 先手，\(Alice\) 和 \(Bob\) 交替进行操作，可行的操作如下：

如果两座山都空了，游戏结束。
如果只有某一座山空了，取走另一座山上的最上面的物品。
如果两座山都没有空，选择任意一座山，并取走其最上面的物品。

假设两人都采取最优策略，请求出 Alice 能取得的物品的价值总和。

题目解析

与上一题类似。

设 \(f[i][j]\)表示 \(A\) 山（从上到下）取到 \(i\) , \(B\) 山（从上到下）取到 \(j\) , \(Alice\) 的最大价值总和，则答案为 \(f[1][1]\) 。

转移，若轮到 \(Alice\) , 即 \((i+j)\%2==0\)，

\(f[i][j]=max(f[i+1][j]+a[i],f[i][j+1]+b[j])\)

否则 \(f[i][j]=min(f[i+1][j],f[i][j+1])\)

再考虑当 \(i=n\) 或者 \(j=m\), 即一座座山已空，此时在两山情况取一种，可用三目运算简化式子。

if((i+j)%2==0) 
    f[i][j]=max((i==n+1)?0:(f[i+1][j]+a[i]),(j==m+1)?0:(f[i][j+1]+b[j]));
else 
    f[i][j]=min((i==n+1)?INF:f[i+1][j],(j==m+1)?INF:f[i][j+1]);

当然，也可以将两座山拼起来，山顶朝外，注意判断一山取完的情况即可。此处不再详细说明。

具体实现

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

const int N=1005;
const int INF=0x3f3f3f3f;
int n,m;
int a[N],b[N];
int f[N][N];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=m;++i) scanf("%d",&b[i]);
	for(int i=n+1;i>=1;--i){
		for(int j=m+1;j>=1;--j){
			if(i==n+1&&j==m+1) continue;
			if((i+j)%2==0)
                f[i][j]=max((i==n+1)?0:(f[i+1][j]+a[i]),(j==m+1)?0:(f[i][j+1]+b[j]));
			else
                f[i][j]=min((i==n+1)?INF:f[i+1][j],(j==m+1)?INF:f[i][j+1]);
		}
	}
	printf("%d\n",f[1][1]);
	return 0;
}

AT-dp-i

传送门

题意简述

\(N\) 枚硬币，第 \(i\) 枚硬币有 \(p_i\) 的概率正面朝上，有 \(1-p_i\) 的概率反面朝上。

扔完所有硬币，求正面朝上的硬币数比反面朝上的硬币数多的概率。

题目解析

也是一种经典DP模型（概率模型）。

设 \(f[i][j]\) 表示前 \(i\) 枚硬币，有 \(j\) 枚是正面朝上的概率，那么答案为 \(\sum_{i=\frac{n}{2}+1}^{n} f[n][i]\)

可以推出转移方程：前 \(i\) 枚硬币，\(j\) 枚正面，第 \(i\) 枚正面朝上概率 \(+\) 第 \(i\) 枚反面朝上概率

\(f[i][j]=f[i-1][j-1] \times p[i]+f[i-1][j] \times (1-p[i])\)

注意 \(f[0][0]=1\)

具体实现

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=3005;
int n;
double p[N];
double f[N][N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%lf",&p[i]);
	f[0][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=i;++j){
		    if(j==0) f[i][j]=f[i-1][j]*(1-p[i]);
			else f[i][j]=f[i-1][j-1]*p[i]+f[i-1][j]*(1-p[i]);
		}
	}
	double sum=0;
	for(int i=(n/2)+1;i<=n;++i) sum+=f[n][i];
	printf("%.10lf\n",sum);
	return 0;
}

AT-abc118-d

传送门

题意简述

有 \(n\) 根火柴, 一共有 \(1-9\) 这 \(10\) 种数字，给出 \(m\)，表示只能用 \(m\) 种数字。接下来是 \(m\) 个能用的数字。数字 \(1,2,3,4,5,6,7,8,9\) 分别需要 \(2,5,5,4,5,6,3,7,6\) 根火柴，要求 \(n\) 根火柴全部都用完且拼成的数字最大，输出这个数字。

题目解析

看到此题，第一反应是完全背包。容量是消耗火柴根数，价值是？

发现要让拼成数字最大，但凡有点数学知识得知位数越多数越大，故首先让位数变多。

设 \(f[i]\) 表示 \(i\) 根火柴在题目给的 \(m\) 种数字中正好用完情况下最多的位数。完全背包计算 \(f\) 数组。

位数相同，从前向后，前面的数越大越好，考虑递归从大到小枚举此位是否能填此数。

即判断 \(f[n]==f[n-id[a[i]]]+1\) （\(n\) 为剩余火柴数，\(id\) 数组表示 \(1-9\) 消耗的火柴数，\(a\) 数组中是数据给出能用的数字，要在枚举前将 \(a\) 数组从大到小排序。）

具体实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10;
int n,m;
int id[10]={0,2,5,5,4,5,6,3,7,6};
int f[N],a[N];
bool cmp(int a,int b){return a>b;}

void out(int n){
	for(int i=1;i<=m;++i){
		if(id[a[i]]>n) continue;
		if(f[n]==f[n-id[a[i]]]+1){
			printf("%d",a[i]);
			out(n-id[a[i]]);
			break;
		}
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) scanf("%d",&a[i]);
	sort(a+1,a+1+m,cmp);
	memset(f,-0x3f,sizeof(f)); 
	f[0]=0;
	for(int i=1;i<=m;++i){
		for(int j=id[a[i]];j<=n;++j){
			f[j]=max(f[j],f[j-id[a[i]]]+1);
		}
	}
	out(n);
	return 0;
}

AT-abc265-e

传送门

题意简述

你现在在一个二维平面，会进行 \(N\) 次传送，每次传送回执行如下移动之一：

移动 \(1\) ：从当前点 \((x,y)\) 移动到 \((x+A,y+B)\)；
移动 \(2\) :从当前点 \((x,y)\) 移动到 \((x+C,y+D)\)；
移动 \(3\) ：从当前点 \((x,y)\) 移动到 \((x+E,y+F)\)。

同时在这个平面上有 \(M\) 个点 \((X_1,Y_1),\ldots,(X_M,Y_M)\) ，这些点是无法停留的。

问 \(N\) 次传送一共会有多少种路径？输出答案对 \(998244353\) 取模。

题目解析

这题与 P1002过河卒有点类似，都是给出一个点能到的其他点，有一些点不能走，求路径数。

但这题的难点是数据范围 \(-10^9\leq X_i,Y_i \leq 10^9\) 。如果设 \(f[i][j]\) 表示从初始格子走到 \((i,j)\) 的路径条数，空间会爆炸。但所幸， \(1 \leq N \leq 300\) ，可以用 \(O(n^3)\) 复杂度的代码通过。

3次方……诶？题目就是给了3种移动方案啊！（高兴地拍起肚皮）

思路就有了，多维DP，设 \(f[i][j][k]\) 表示从初始点走了 \(i\) 次移动 \(1\)，\(j\) 次移动 \(2\) ，\(k\) 次移动 \(3\) 时的路径数。枚举 \(0\leq i,j,k\leq N\) 且 \(i+j+k\leq N\) ，转移时判断边界和是否能经过即可。

判断是否能经过可用哈希，我太懒用了 \(map\) ，注意若不会二维 \(map\) 可以将点 \((i,j)\) 存储为 \(i\times10^9+j\) （因为 \(i,j\) 最大 \(10^9\) ，一定不会冲突。）

具体实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
const int p=1e9;
const int mod=998244353;
const int N=305;
#define ll long long
int n,m;
int a,b,c,d,e,f;
ll x,y;
map<ll,int> ma;
ll dp[N][N][N],ans;

inline ll check(int i,int j,int k){return (1ll*i*a+1ll*j*c+1ll*k*e)*p+(1ll*i*b+1ll*j*d+1ll*k*f);}

int main(){
	scanf("%d%d%d%d%d%d%d%d",&n,&m,&a,&b,&c,&d,&e,&f);
	for(int i=1;i<=m;++i){
		scanf("%lld%lld",&x,&y);
		ma[x*p+y]=1;
	}
	dp[0][0][0]=1;
	for(int i=0;i<=n;++i){
		for(int j=0;j<=n-i;++j){
			for(int k=0;k<=n-i-j;++k){
				if(ma[check(i,j,k)]) continue;
				if(i>0) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k])%mod;
				if(j>0) dp[i][j][k]=(dp[i][j][k]+dp[i][j-1][k])%mod;
				if(k>0) dp[i][j][k]=(dp[i][j][k]+dp[i][j][k-1])%mod;
				if(i+j+k==n) ans=(ans+dp[i][j][k])%mod;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}

~ 撒花qwq ~

标签：const,入门,int,d%,Alice,DP,include,dp
From： https://www.cnblogs.com/Mr-KaYa/p/17398379.html

AT-abc286-d

AT-dp-l

AT-tdpc-game

AT-dp-i

AT-abc118-d

AT-abc265-e

相关文章

赞助商

阅读排行