首页 > 其他分享 >AT dp 26 题 题解

AT dp 26 题 题解

时间：2023-01-31 12:34:42浏览次数：76  
标签：26 int 题解 typedef long maxn dp define

题单：https://www.luogu.com.cn/training/100578#problems

嘛虽然是 26 题，但是简单的题就不想写了...
就写绿题及以上的吧

目录

E

对重量 dp，设 \(dp[i][v]\) 表示考虑到前 \(i\) 个物品，价值为 \(v\) 时的最小重量

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f,maxn=105;

int n,W,w[maxn],v[maxn];
int dp[105][100005];
signed main(){
	memset(dp, 0x3f, sizeof dp);
	scanf("%d%d",&n,&W);
	for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);
	dp[0][0] = 0;
	for(int i=1;i<=n;i++){
		for(int j=0;j+v[i]<=100000;j++){
			dp[i][j + v[i]] = min(dp[i][j + v[i]], dp[i-1][j] + w[i]);
		}
		for(int j=0;j<=100000;j++)dp[i][j] = min(dp[i][j], dp[i-1][j]);
	}
	for(int i=100000;i>=0;i--)
		if(dp[n][i]<=W)return printf("%d\n",i),0;

	return 0;
}

I

\(dp[i][j]\) 表示考虑到前 \(i\) 个，翻到正面的有 \(j\) 个的概率

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f,maxn=3005;

int n;
double p[maxn],dp[maxn][maxn];
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lf",&p[i]);
	dp[0][0] = 1.0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i;j++){
			dp[i][j] += dp[i-1][j] * (1-p[i]);
		}
		for(int j=1;j<=i;j++){
			dp[i][j] += dp[i-1][j-1] * p[i];
		}
	}
	double res=0.0;
	for(int i=n/2+1;i<=n;i++)res+=dp[n][i];
	printf("%.10f\n",res);

	return 0;
}

J

\(dp[b][c][d]\) 表示盘子里还剩 \(b,c,d\) 个 \(1,2,3\) 个寿司时，全拿走的期望步数
期望题一般都是逆推，\(dp[0][0][0]=0\)
考虑一般情况：$$dp[b][c][d]=1+\frac{a}{n}dp[b][c][d]+\frac{b}{n}dp[b-1][c][d]+\frac{c}{n}dp[b+1][c-1][d]+\frac{d}{n}dp[b][c+1][d-1]$$，消元可得 $$dp[b][c][d]=\frac{b}{b+c+d}dp[b-1][c][d]+\frac{c}{b+c+d}dp[b+1][c-1][d]+\frac{d}{b+c+d}dp[b][c+1][d-1]+\frac{n}{b+c+d}$$

答案就是 \(dp[a[1]][a[2]][a[3]]\)

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;

int n,b[5];
double dp[302][302][302];

signed main(){
	int r=0;
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++)scanf("%d",&x),++b[x],r+=x;
	for(int tn=1;tn<=r;tn++){
		for(int i=0;i<=n;i++){
			for(int j=0;j<=n;j++){
				int k=tn-i-2*j;
				if(k%3)continue;
				k /= 3;
				if(k < 0 || k > n)continue;
				if(i)dp[i][j][k] += 1.0 * dp[i-1][j][k] * i/(i+j+k);
				if(j)dp[i][j][k] += 1.0*dp[i+1][j-1][k] * j/(i+j+k);
				if(k)dp[i][j][k] += 1.0*dp[i][j+1][k-1] * k/(i+j+k);
				dp[i][j][k] += 1.0 * n / (i+j+k);
			}
		}
	}
	printf("%.15f\n",dp[b[1]][b[2]][b[3]]);

	return 0;
}

M

\(O(n^2)\) dp 显然，发现这是个前缀和的形式，因此可以前缀和优化 dp

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f,mod=1e9+7,maxn=100005;

int n,k,a[maxn];
int dp[maxn], sum[maxn];
signed main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	dp[0] = sum[0] = 1;
	for(int i=1;i<=k;i++)sum[i]=1;
	for(int i=1;i<=n;i++){
		for(int j=k;j>=1;j--){
			// dp[j] += dp[j-a[i]]+..+dp[j-1]
			(dp[j] += (sum[j-1] - ((j-a[i]-1 < 0) ? 0 : sum[max(0, j-a[i]-1)]) + mod)%mod) %= mod;
		}
		for(int j=1;j<=k;j++)sum[j] = sum[j-1] + dp[j], sum[j] %= mod;
	}
	cout<<dp[k];

	return 0;
}

O

平平无奇状压dp，记搜一下即可

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn=23, mod=1e9+7;

int n,a[maxn][maxn];
int b[25][25],cnt[222];

int dp[22][(1<<21)+5];
int dfs(int x, int S){
	if(x==n+1)return 1;
	int &ddd = dp[x][S];
	if(~ddd)return ddd;
	
	int dd=0;
	for(int i=1;i<=cnt[x];i++){int it=b[x][i];if((S & (1<<(it-1)))==0){
		(dd += dfs(x+1, S ^ (1<<(it-1))));
		if(dd >= mod)dd -= mod;
	}}
	return ddd=dd;
}

signed main(){
	memset(dp,-1,sizeof dp); 
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			scanf("%d",&a[i][j]);
			if(a[i][j])b[i][++cnt[i]]=j;
		}
	ll res = dfs(1, 0);
	cout<<res;

	return 0;
}

P

\(dp[i][0/1]\) 表示 \(i\) 号点黑/白的方案数，注意转移需要用乘法原理

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f,maxn=2e5+5,mod=1e9+7;

int n;
vector<int>g[maxn];
ll dp[maxn][2],vis[maxn];

void dfs(int x,int fat=0){
	vis[x]=1;
	dp[x][0]=dp[x][1]=1;
	
	for(auto u : g[x])if(u!=fat){
		dfs(u, x);
		(dp[x][0] *= dp[u][1]) %= mod;
		(dp[x][1] *= (dp[u][0] + dp[u][1])) %= mod;
	}
}

signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++){
		int x,y;scanf("%d%d",&x,&y);
		g[x].pb(y), g[y].pb(x);
	}
	ll ans=0;
	for(int i=1;i<=n;i++)if(!vis[i]){
		dfs(i);
		(ans+=dp[i][0]+dp[i][1])%=mod;
	}
	cout<<ans;

	return 0;
}

Q

从数据范围很难想到是 dp 啊。。。
设 \(dp[i][j]\) 表示考虑到前 \(i\) 个花，选最后一个花的高度是 \(j\) 的最大价值
\(dp[i][j] = \min{dp[p][k]} + h[i], p<i \and k<j\)
发现其实第一维可以省略，因为转移到 \(i\) 的时候肯定 \(dp\) 数组存的是前面的 \(j\)

再设 \(dp[i]\) 表示考虑到前 \(i\) 个花，且最后一个花的位置是 \(i\) 的最大价值
\(dp[i] = \min{dp[j]} + h[i], h[j]<h[i]\)
这样转移是 \(O(n^2)\) 的，怎么优化？
如果我们把 \(dp\) 看成 \(dp[h[i]]\)，那么能转移到 \(i\) 的 \(j\) 其实是 \(dp[..<h[i]]\)，考虑使用线段树优化
线段树每个点 \(i\) 存的是 \(dp[i]\) 但是这个点代表的是 \(h\) 值，\(dp[i]\) 就是当前点高度为 \(i\) 且选了的时候的最大价值

转移就用线段树求一下前缀 max 即可，因为 'j' 其实就是 \(h[j]<h[i]\) 的点，转移到线段树上就是 \(j<i\) 的点

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5+5;

int n,h[maxn],a[maxn];
struct segm{
	ll mxf;
	segm(){mxf=0;}
}se[maxn << 2];
ll dp[maxn];

void update(int x,ll to,int l,int r,int num){
	if(l == r){
		se[num].mxf = to;
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid)update(x,to,l,mid,num<<1);
	else update(x,to,mid+1,r,num<<1|1);
	se[num].mxf = max(se[num << 1].mxf, se[num << 1 | 1].mxf);
}

ll query(int x,int y,int l,int r,int num){
	if(x <= l && r <= y)return se[num].mxf;
	int mid=l+r>>1;
	if(y<=mid)return query(x,y,l,mid,num<<1);
	else if(x>mid)return query(x,y,mid+1,r,num<<1|1);
	else return max(query(x,y,l,mid,num<<1), query(x,y,mid+1,r,num<<1|1));
}

signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&h[i]);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	
	ll r=0;
	for(int i=1;i<=n;i++){
		ll qu = query(1, h[i], 1, n, 1);
		dp[i] = qu + a[i];
		r = max(r, dp[i]);
		update(h[i], dp[i], 1, n, 1);
	}
	cout << r;
	
	return 0;
}

R

设 \(dp[i][j]\) 表示 \(i\rightarrow j\) 的长度为 \(k\) 的方案数
\(k\rightarrow k+1\)：\(ndp[i][j]=\sum_k{dp[i][k]\times a[k][j]}\)，而 \(a\) 就是邻接矩阵，为0/1
发现这就是矩阵乘法的形式，因此对原邻接矩阵求 \(k\) 次方即可

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, mod = 1e9+7;

int n;ll k;
struct mat{
	ll a[52][52];
	mat(){memset(a,0,sizeof a);}
};
mat b;

mat operator * (mat a, mat b){
	mat c;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				(c.a[i][j] += a.a[i][k] * b.a[k][j] % mod) %= mod;
	return c;
}

mat pw(mat b, ll k){
	mat bs = b, c = b;-- k;
	while(k){
		if(k&1)c = c * bs;
		bs = bs * bs;
		k >>= 1;
	}
	return c;
}

signed main(){
	cin >> n >> k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)cin >> b.a[i][j];
	
	mat now = pw(b, k);
	
	ll ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)(ans += now.a[i][j]) %= mod;
	cout<<ans;

	return 0;
}

S

随便数位 dp 一下...

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, mod = 1e9+7;

char s[10005];
int num[10005], d, n;
ll dp[10005][2][2][105];

ll dfs(int x,int up,int is0,int rem){
	ll &dd = dp[x][up][is0][rem];
	if(x == n+1){
		if(is0 || rem)return dd = 0;
		else return dd = 1;
	}
	if(~dd)return dd;
	
	dd = 0;
	int lim = up ? num[x] : 9;
	for(int i=0;i<=lim;i++){
		(dd += dfs(x+1, up && i == lim, is0 && i == 0, (rem + i) % d)) %= mod;
	}
	return dd;
}

signed main(){
	memset(dp, -1, sizeof dp);
	scanf("%s",s + 1);
	scanf("%d",&d);
	n = strlen(s + 1);
	for(int i=1;i<=n;i++)num[i] = s[i] - '0';
	printf("%d\n",dfs(1,1,1,0));

	return 0;
}

T

很有意思的一道题
设 \(dp[i][j]\) 表示考虑到第 \(i\) 位，且最后一位在 \(1..i\) 中是第 \(j\) 位的方案数
注意这里，因为我们只关注排列的相对大小，因此可以用相对的排名来计算方案

\[dp[i][j] = \sum_{k=1}^{j-1}dp[i-1][k], s[i]为< \]

\[dp[i][j] = \sum_{k=j}^{i-1}dp[i-1][k], s[i]为> \]

因为每次转移都是合法的，因此每个状态对应的方案数都是合法的方案数
前缀和优化一下即可

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 3005, mod = 1e9+7;

ll dp[3005][3005];
int n;
char s[3005];
ll sum[3005];

signed main(){
	scanf("%d",&n);scanf("%s",s + 2);
	dp[1][1] = sum[1] = 1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			if(s[i] == '<')dp[i][j] = sum[j-1];
			else dp[i][j] = sum[i-1] - sum[j-1] + mod, dp[i][j] %= mod;
		}
		for(int j=1;j<=i;j++)sum[j] = sum[j-1] + dp[i][j], sum[j] %= mod;
	}
	ll ans = 0;
	for(int i=1;i<=n;i++)(ans += dp[n][i]) %= mod;
	cout << ans;

	return 0;
}

U

枚举子集的 \(O(3^n)\) trick

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 18, maxm = (1<<16) + 5;

int n;
int a[maxn][maxn];
ll cap[maxm], dp[maxm];
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);
	for(int S=0;S<=(1<<n)-1;S++){
		for(int i=1;i<=n;i++)
			for(int j=1;j<i;j++)
				if((S & (1<<i-1)) && (S & (1<<j-1)))
					cap[S] += a[i][j];
	}
	dp[0] = 0;
	for(int S=1;S<=(1<<n)-1;S++){
		for(int T=S;T;T=(T-1)&S){
			dp[S] = max(dp[S], dp[T] + cap[S ^ T]); 
		}
		dp[S] = max(dp[S], cap[S]);
	}
	cout << dp[(1<<n)-1];

	return 0;
}

V

换根dp

标签：26,int,题解,typedef,long,maxn,dp,define
From： https://www.cnblogs.com/SkyRainWind/p/17078594.html

相关文章

  • uniapp webview中动态设置公众号文章标题不显示问题解决
    设置在onLoad中可能会引起偶发性无效。解决方案：1、改写在onReady生命周期中。2、用setTimeout设置延迟。 onReady(){this.timers=setTimeout(()=>{......
  • 【双指针】LeetCode 26. 删除有序数组中的重复项
    题目链接26.删除有序数组中的重复项思路设定两个指针i和j，使用j遍历数组，将与前项不相等的元素放到i的位置。代码、classSolution{publicintremoveDup......
  • NAPT网络结构下TCP/UDP/ICMP访问外网原理思考
    背景作为程序员，应该都听说过NAT(NetworkAddressTransfer，网络地址转换)这一技术名词，并或多或少大概知道其原理与作用--NAT是用于解决IPv4地址不够用，保证我们能够在IPv6普......
  • USACO2023 Bronze 题解
    Problem1.Leaders\(\mathcal{Farmer\John}\)共有\(n\)头奶牛，品种用字符\(\mathsf{G}\)或\(\mathsf{H}\)表示。每一头牛有一个管辖区间\([i,E_i]\)称一头......
  • 算法：线段树&&Luogu p3372题解
    前言不愧是线段树，竟然卡我这么久，还是那句话：十年OI一场空，不开longlong见祖宗#1什么是线段树？线段树长什么样？通俗一点，线段树就是线段，树。实际上，线段树是一棵完全......
  • 問題　ｌ26
    １．ありましたーあったんです２．ありませんーなかったんです３．すきですすきなんです  １．どこで買ったんですか２．何歳にないたんですか３．どのくらい帰るんですか４．何人が......
  • CF1067E 题解
    题意传送门给定一棵\(n\)个节点的树，每条边有\(\frac{1}{2}\)的概率出现，可以得到一个森林，求这个森林邻接矩阵的秩的期望。\(1\len\le5\times10^5\)。题解此题关键......
  • [AHOI2022] 山河重整 题解
    T3，一个不错的数学题，给了不少的暴力分。Statement求有多少值域为\([1,n]\)的集合，01背包可以凑出\(1\simn\)中的所有数字。Subtask\(1\sim6\)我们从小到大选择每......
  • leetcode简单(数组、字符串)：[219, 268, 349, 414, 485, 541, 557, 821, 925, 977]
    目录219.存在重复元素268.丢失的数字349.两个数组的交集414.第三大的数485.最大连续1的个数541.反转字符串II557.反转字符串中的单词III821.字符的最短距离925......
  • 微信小程序-【转发好友】以及中文标题乱码问题解决
    微信小程序的转发功能，参考官方文档，使用的buttom的open-type功能，下面是转发功能的具体实现。//通过按钮的open-type="share"实现转发，触发onShareAppMessage函数<butto......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99