首页 > 其他分享 >DP做题合集

DP做题合集

时间:2023-01-29 12:23:47浏览次数:49  
标签:状态 纪念品 int 做题 DP include 合集 dp

第一题 P7074 [CSP-J2020] 方格取数

做法【dp】

阶段

因为只能往左不能往右,所以我们可以以一列作为一个阶段。

又因为路线不能重复,所以在一列之中,只能一直向上或一直向下,所以我们分类讨论。

PS:妙啊,通过分类讨论来解决路径的后效性问题。

状态定义

\(dp_{i,j,t}\) 表示位于第 \(i\) 行 ,第 \(j\) 列,当 \(t\) \(=\) \(1\) 时,表示从上方来到当前格,当 \(t\) \(=\) \(0\) 时,表示从下方来到当前格,时得到的最大值。

状态转移方程

当 \(t = 1\) 时:

\(dp_{i,j,t} = \max (dp_{i,j-1,0},dp_{i,j-1,1},dp_{i-1,j,1}) + a_{i,j}\)

当 \(t = 0\) 时:

\(dp_{i,j,t} = \max (dp_{i,j-1,0},dp_{i,j-1,1},dp_{i+1,j,0}) + a_{i,j}\)

初始化

因为起点在左上角,所以第一列只能自上往下走。

$dp_{i,1,1} = dp_{i-1,1,1} + a_{i,1} $

code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
ll n,m;
ll a[1005][1005],v[1005][1005][2],f[1005][1005];
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=m;j++) scanf("%lld",&a[i][j]);
	memset(v,0xcf,sizeof(v));
	for(int i=1;i<=n;i++) f[i][1]=f[i-1][1]+a[i][1];
	for(int j=2;j<=m;j++){
		for(int i=1;i<=n;i++) v[i][j][1]=max(f[i][j-1],v[i-1][j][1])+a[i][j];
		for(int i=n;i>=1;i--) v[i][j][0]=max(f[i][j-1],v[i+1][j][0])+a[i][j];
		for(int i=1;i<=n;i++) f[i][j]=max(v[i][j][0],v[i][j][1]); 
	}
	cout<<f[n][m]<<endl;
	return 0;
}

summary

这道题与普通的区间 \(DP\) 不同,不止可以往左,往下走,还可以往上走,这样就无法满足 \(DP\) 的无后效性。

为了解决这个问题,于是采用了分类讨论的方法。

因为只能往左,所以我们可以把每列分成一个阶段。因为路径不能重叠,所以对于每一列,只能一直向上或者一直向下

于是我们在正常的区间 \(DP\) 上再加一维来记录向上 or 向下走。

\(2022.8.17\)

第二题 P5662 [CSP-J2019] 纪念品

思路分析

题目中说了,求在最后将所有纪念品卖掉后能拥有的最多金币数量。

那么我们就可以设 \(dp_{i}\) 表示在第 \(i\) 天把所有纪念品都卖掉后能拥有的最多金币的数量。

由于对于第 \(i-1\) 天,卖出纪念品和买入纪念品的价格相同,因此,我们可以在第 \(i-1\) 天先将手上所有的纪念品都卖掉。然后利用与次日相同纪念品的价格差挑选最佳纪念品从中赚取利润(是的,这就叫中间商赚差价)。即可求出第 \(i\) 天初始得到的最大金币(这里指的也是在第 \(i\) 天将所有纪念品卖掉后的,即\(dp_i\) )。

那么他的状态转移方程就是:

\(dp_{i}=\max\){\(dp_{i-1}-在 i-1 天买纪念品的总花费+在第 i 天卖纪念品所得到的总收益\)}

还有变量无法表示出来,我们就将他加入状态转移方程中。(相信有聪明的小朋友已经看出来接下来就是标准的完全背包了)

\(dp_{i,j}\) 表示用第 \(i\) 天把所有纪念品都卖掉后能拥有的最多金币花费\(j\)元购买纪念品所能得到的最大价值。

花费的是第 \(i\) 天购买纪念品的价格,得到的价值为第 \(i+1\) 天卖出后得到的收益。

对于一个纪念品 \(k\) 。

\(dp[i][j]=\max(dp[i][j],dp[i][j-val[i][k]]+val[i+1][k])\)

第 \(i+1\) 天能得到的最多金币数为:

\(ans=max(ans,num-j+dp[i][j])\)

\(num\) 是第 \(i\) 天获得的最大金币数, \(ans\) 是第 \(i+1\) 天能得到的最多金币数。

写代码的过程中可以发现我们己经枚举了天数\(t\),且在状态转移方程中 \(i\) 丝毫不动,因此可以将其省略。

code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int T,n,m;
int dp[10005],val[105][1005];
int main(){
	scanf("%d%d%d",&T,&n,&m);
	for(int i=1;i<=T;i++)
		for(int j=1;j<=n;j++) scanf("%d",&val[i][j]);
	
	int ans=m;
	for(int t=1;t<T;t++){
		memset(dp,0xcf,sizeof(dp));
		dp[0]=0;
		for(int i=1;i<=n;i++){
			for(int j=val[t][i];j<=ans;j++){
				dp[j]=max(dp[j],dp[j-val[t][i]]+val[t+1][i]);
			}
		}
		int num=ans;
		for(int i=1;i<=num;i++) ans=max(ans,num-i+dp[i]);
	}
	cout<<ans<<endl;
	return 0;
}

summary

通过这题,我们可以总结出,一题DP可以先将状态设为题目要求的东西,再列出状态转移方程。如果状态转移方程有些部分无法表示出来,就将他加入状态之中。

\(2022.8.18\)

第三题 P1018 [NOIP2000 提高组] 乘积最大

前言

事先声明!博主是不会写高精的屑。因此此题只拿到了开 \(LL\) 的 \(\color{orange}{60}\) 分。

但这并不妨碍我练 \(DP\)。

思路辨析

很容易想到,以前 \(i\) 个数的部分作为一个阶段变量。

有了具体的数量,又很自然的想到将钥匙的个数作为一个变量加进去,也就是 \(j\) 。

诶,好像能行,再看看。

综上,\(dp_{i,j}\) 表示的是前 \(i\) 个数用 \(j\) 个乘号隔开所能得到的最大乘积。

设想一下,当我们知道如上所述的信息时,要怎么通过它得到下一阶段的信息,或它是如何由其它阶段推来的呢?

显然第二种更好推。

已知钥匙的个数,枚举最后一个钥匙所在的位置(这里记为 \(r\) ),可以将前 \(i\) 个数分成两部分。

前半部分是前 \(r\) 个数用 \(j-1\) 个乘号断开所得到的乘积最大值,后半部分则是 \(N\) 个字符中第 \(r+1\) 个字符到第 \(i\) 个字符所组成的数,用两者之积来更新答案。

因此,状态转移方程为

\(dp_{i,j} = \max( dp_{r,j-1} * nu_{r+1,i} , dp_{i,j})\).

注:\(nu_{r+1,i}\)就是 \(N\) 个字符中第 \(r+1\) 个字符到第 \(i\) 个字符所组成的数。

code

#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
ll n,k,a[45],nu[45][45],dp[45][10];
int main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++) scanf("%1d",&a[i]);//“%1d”每次只读一个数字
	
	for(int i=1;i<=n;i++) nu[i][i]=a[i];
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			nu[i][j]=nu[i][j-1]*10+a[j];
		}
	}
	
	//这一段是对nu的预处理
	
	for(int i=1;i<=n;i++) dp[i][0]=nu[1][i];//初始化
	
	for(ll i=1;i<=n;i++){
		for(int j=1;j<min(i,k+1);j++){//i个数最多只能放i-1个乘号,所以和k+1取min
			for(int r=1;r<i;r++){
				dp[i][j]=max(dp[r][j-1]*nu[r+1][i],dp[i][j]);
			}
		}
	}
	cout<<dp[n][k]<<endl;
	return 0;
}

summary

对状态的描述好像有进步!继续加油!

\(2022.12.27\)

第四题 P1586 四方定理

思路分析

对于一个数 \(i\) ,它可能由 \(j\) (\(1\le j \le 4\)) 个平方数组成。

我们不妨设 \(dp_{i,j}\) 为数 \(i\) 由 \(j\) 个平方数所组成的方案。

那么很容易想到 \(dp_{i,j} += dp_{i-k*k,j-1}\) \((k*k\le i)\)。即枚举所有小于 \(i\) 的平方数,加上包含其的方案数。

于是我们就能得到以下代码

	dp[0][0]=1;
	for(int i=1;i<=32768;i++){
		for(int j=1;j<=4;j++){
			for(int k=1;k*k<=i;k++){
					dp[i][j]+=dp[i-rec[k]][j-1];
			}
		}
	}

乍看似乎没什么问题。但输入 \(5\) 后会发现,标准答案是 \(1\) ,输出却是 \(2\)。

这是怎么回事呢?仔细研究后会发现。如果这么枚举的话,$5=2^2 + 1^2 $ 和 \(5 = 1^2+2^2\) 被当成两种方案被统计了两次。

此时,需要交换枚举顺序,令一种方案被其和数中的最高次方平方数累计。

简单来说,就是令 \(5\) 被 \(2^2\) 统计,而不是 \(1^2\) 。

于是乎得到以下代码。

	dp[0][0]=1;
	for(int i=1;i*i<=32768;i++){
		for(int j=i*i;j<=32768;j++){
			for(int k=1;k<=4;k++){
				dp[j][k]+=dp[j-rec[i]][k-1];
			}
		}
	}

至此,此题就可以 \(\color{green}{AC}\) 啦。

code

点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int rec[32770],dp[32770][5];
int t,n;
int main(){
	scanf("%d",&t);
	for(int i=1;i*i<=32768;i++) rec[i]=i*i;
	dp[0][0]=1;
	for(int i=1;i*i<=32768;i++){
		for(int j=i*i;j<=32768;j++){
			for(int k=1;k<=4;k++){
				dp[j][k]+=dp[j-rec[i]][k-1];
			}
		}
	}
	for(int i=1;i<=t;i++){
		scanf("%d",&n);
		int num=0;
		for(int j=1;j<=4;j++) num+=dp[n][j];
		cout<<num<<endl;
	}
	return 0;
} 

summary

对于去重似乎打开了新世界的大门。

仔细回想,通过规定顺序来去重的方法已经不是第一次见了。

在深搜中我们经常通过增加变量 \(last\) 来固定枚举顺序以达到剪枝的作用。这里剪掉的,恰好就是重复的方案。

在质数筛中,线性筛法就是通过保证每个合数 \(i * p\) 只会被它最小质因子 \(p\) 筛一次,从而优化掉了被重复筛的合数。和此题是不是有着异曲同工之妙!

\(2023.1.2\)

第五题 P2426 删数

题目分析

由于对于题目所得的最优删法,与删除的顺序无关,因此我们可以默认从前往后删片段。

设 \(dp_i\) 表示删除前 \(i\) 个数所得到的最大价值。

对于第 \(i\) 个数,它可以选择独自删除 \(i\) 。状态转移方程为

$ dp_i $ \(=\) $ dp_{i-1}$ \(+\) \(a_i\) 。

亦可以选择与前面的数一起删掉。求此时与哪几个数一起删得最大值。

\(dp_i\) \(=\) $dp_{j-1} + $$abs (a_i-a_j)*(i-j+1)$ \((1\le j < i)\)

表示删除 \(j-i\) 段的数。

code

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a[105],dp[105];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	dp[1]=a[1]; 
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			dp[i]=max(dp[i],dp[j-1]+abs(a[i]-a[j])*(i-j+1));
		}
		dp[i]=max(dp[i],dp[i-1]+a[i]);
	}
	cout<<dp[n]<<endl;
	return 0;
} 

summary

今天这题看似很简单,想明白却不容易。

本来一开始定义的是 \(dp_{i,j}\) 表示删除 \(i-j\) 段所获得的最大价值。

但接下来就遇到难点了,我们要如何枚举断点 \(k\) 。

如果只是将断点 \(k\) 看做将 \(i-j\) 字符分成两端所得到的最大价值,那可出大问题了。

对于一段字符,它的最优断法不一定是断成两段。

但是,若断点\(k\)表示其中有一段删除的是\(k-j\),而删除\(i-(k-1)\) 段所获得的最大价值为 \(dp_{i,k-1}\) 。这...状态转移方程不就又出来了。

至此,根本思路与题目分析已无差别。

因此,在思考问题时,一定要注意从问题本身出发,来找状态转移方程。

\(2023.1.2\)

第六道 P1005 [NOIP2007 提高组] 矩阵取数游戏

前言

今天依旧是不写高精的一天呢!(是的,这位作者又只拿了开 \(LL\) 的 \(\color{yellow}{60}\) 分)

思路描述

看到数据 \(n,m \le 80(30)\) 就知道数组可以任性开,心理有个底后,再来看题目。

状态描述

首先肯定要来一个 \(dp_{i,j}\) 来表示第 \(i\) 次时取第 \(j\) 行的数。

对于每一次放置,我们要考虑到的是之前每一次都取到什么,也就是现在的头和尾分别是哪两个数

想明白这一点,就可以描述状态了。

\(dp_{i,j,k,t}\) 表示第 \(i\) 次时取第 \(j\) 行的数,对于第 \(j\) 行,它的行首被取了 \(k\) 个数,他的行尾被取了 \(t\) 个数。

由于 $t = i - k $ ,当 \(i,k\) 确定时,\(t\) 也一定唯一,因此可以省略。

状态转移方程

描述出状态了,状态转移方程还会远吗?

显然有

\(dp_{i,j,k} = \max(dp_{i-1,j,k-1}+val(i,j,k),dp_{i-1,j,k}+val(i,j,m-(i-k)+1))\)。

\(val(x,y,z)\) 表示第 \(x\) 次时取位于第 \(y\) 行第 \(z\) 列的数所能获得的得分。

\(\max\) 中的两者分别对应了第 \(i\) 次时,在第 \(j\) 行取队首 \(or\) 队尾的情况。

code

#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int n,m;
ll a[85][85],dp[85][85][85];
int bas[31];
int main(){
	scanf("%d%d",&n,&m);
	bas[0]=1;
	for(int i=1;i<=30;i++) bas[i]=bas[i-1]*2;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
		
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			dp[i][j][i]=dp[i-1][j][i-1]+a[j][i]*bas[i],dp[i][j][0]=dp[i-1][j][0]+a[j][m-i+1]*bas[i];//这两种情况比较特殊,所以单独列。
			for(int k=1;k<i;k++){
				dp[i][j][k]=max(dp[i-1][j][k-1]+a[j][k]*bas[i],dp[i-1][j][k]+a[j][m-(i-k)+1]*bas[i]);
			}
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		ll max_num=0;
		for(int j=0;j<=m;j++)
			max_num=max(max_num,dp[m][i][j]);
		ans+=max_num;
	}
	cout<<ans<<endl;
	return 0; 
}

ps:经过作者后续习惯性翻翻题解(发现原来区间DP也可以做),以及打输出时的共同启发,发现实际上我们只需要分别枚举对于每一行是的最优解,加起来就可以了。因此状态中表示行的那一维可以省略。然后就有了以下代码。

#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int n,m;
ll a[85][85],dp[85][85];
int bas[31];
int main(){
	scanf("%d%d",&n,&m);
	bas[0]=1;
	for(int i=1;i<=30;i++) bas[i]=bas[i-1]*2;

	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);

	ll ans=0,max_num;	
	for(int j=1;j<=n;j++){
		
		for(int i=1;i<=m;i++){
			dp[i][i]=dp[i-1][i-1]+a[j][i]*bas[i],dp[i][0]=dp[i-1][0]+a[j][m-i+1]*bas[i];
			for(int k=1;k<i;k++){
				dp[i][k]=max(dp[i-1][k-1]+a[j][k]*bas[i],dp[i-1][k]+a[j][m-(i-k)+1]*bas[i]);
			}
		}
		max_num=0;
		for(int i=0;i<=m;i++) max_num=max(max_num,dp[m][i]);
		ans+=max_num;
	}
	
	cout<<ans<<endl;
	return 0; 
}

事实上没太大区别,毕竟它的数据范围可以让我任性开(首尾呼应.jpg(确信))。

summary

对于省略维数有了更深刻的理解。

  • 可以用其他维度表示的可以省略。

  • 可以通过分开解决时不需要整体来定义。

\(2023.1.12\)

第七、八道 P1352 没有上司的舞会+P1122 最大子树和(树形DP入门)

前言

今日偶然打开 \(oi-wiki\),发现树形 \(DP\) 例题正好是之前在洛谷上鸽着的一道题。所以......

\(\color{red}{很高兴以这样的方式认识你,树形 DP !}\)

这例题造的太好了,简直是无痛入门(感动.jpg)

P1352 没有上司的舞会

题目传送门~

思路剖析

状态定义

\(dp_i\) 表示的是以 \(i\) 为根节点的子树所获得的最大价值。

由于每个节点代表着一位人物,有来与不来两种状态,所以再加一维状态变量。

\(dp_{i,0}\) 表示以 \(i\) 为根节点的子树所能获得的最大价值,且这位人物没来。 \(dp_{i,1}\) 则对应来了的状态。

状态转移方程

 现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 r_i。
 但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。

根据题意描述,容易得出状态转移方程:

\(dp_{i,0} += max (dp_{j,0},dp_{j,1})\)

\(dp_{i,1} += dp_{j,0}\)

\(j\) 指的是 \(i\) 的子节点,且显然 \(dp_{i,1}\) 的初始值为 \(r_i\)。

code

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a[6005];
int head[6005],nex[6005],edge[6005],tot;
int vis[6005],dp[6005][2];
void dfs(int x){
	dp[x][1]=a[x];
	for(int i=head[x];i;i=nex[i]){
		int y=edge[i];
		dfs(y);
		dp[x][1]+=dp[y][0];
		dp[x][0]+=max(dp[y][0],dp[y][1]);
	}
	return;
} 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<n;i++){
		int l,k;
		scanf("%d%d",&l,&k);
		nex[++tot]=head[k];
		head[k]=tot;
		edge[tot]=l;
		vis[l]=1;
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i);
			cout<<max(dp[i][0],dp[i][1])<<endl;
			return 0;
		}
	}
}

P1122 最大子树和

题目传送门~

思路剖析

谁是根节点

由于这题是无向图(但由于以 \(n-1\) 条边相连接,所以本质与树并无太大区别),所以要讨论以谁作为根节点。

根节点之所以重要,是因为在递归过程中,我们已经默认根节点所代表的那束花已经被保留了,但根节点代表的花不一定在最优解的集合之中。

仔细模拟后,不难发现,对于以 \(i\) 为根节点的子树,\(dp_i\) 往下为最优解,而往上由于还未更新,因此相当于剪去 \(dp_i\) 与其根节点的枝桠。

进一步推理,无论通过哪个节点作为根节点,再递归的过程中,其实已经变相枚举了将其剪去的种种情况,所以,只需要在过程中取最优解即可。

状态定义+状态转移方程

这点比较好理解,所以合并在一起阐述。

\(dp_i\) 表示以 \(i\) 为根节点的子树所获得的最大美丽值。

显然有

\(dp_i+=max(dp_j,0)\)。

\(j\) 为子节点,当其所带来的价值为负数时,不如直接剪掉。

code

有几处雷点在注释中标记出来了(都是血泪教训啊QAQ)

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,ans=-0x3f3f3f3f;//答案可能为负!要初始化为负无穷
int head[16005],nex[35005],edge[35005],tot;//由于是双向边,所以空间要开双倍
int dp[16005],vis[16005];
void dfs(int x){
	vis[x]=1;//不要在循环内标记,否则标记不到根节点本身。
	for(int i=head[x];i;i=nex[i]){
		int y=edge[i];
		if(vis[y]) continue;
		dfs(y);
		if(dp[y]<=0) continue;
		dp[x]+=dp[y]; 
	}
	ans=max(ans,dp[x]);
	return;
} 
void add(int l,int k) {nex[++tot]=head[k],head[k]=tot,edge[tot]=l;}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&dp[i]);
	for(int i=1;i<n;i++){
		int l,k;
		scanf("%d%d",&l,&k);
		add(l,k);
		add(k,l);
	}
	dfs(1);
	cout<<ans<<endl;
	return 0;
}

\(2023.1.18\)

第九题 P1387 最大正方形

题目分析

设 \(dp_{i,j}\) 表示以 \(i,j\) 为右下角的最大正方形的边长。

状态转移方程为:

\(dp_{i,j} = \min(dp_{i,j-1},dp_{i-1,j},dp_{i-1,j-1})+1\)

为什么取最大边长却要用 \(\min\) 来转移呢?

因为在三者中取最小,等于另外两者一定大于最小的值,不需要考虑另外两者比边长小的问题。且以最小的值 \(+1\) 为边长进行状态转移,一定会形成为以 \(i,j\) 为右下角的最大正方形,再大一点都不符合条件,不会形成正方形。

code


#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,dp[105][105],a[105][105],ans;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]) dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1;
			ans=max(ans,dp[i][j]);
		}
	}
	cout<<ans<<endl;
	return 0;
}

\(2023.1.29\)

第十题 P3147 [USACO16OPEN]262144 P

题目分析

此题为区间 \(DP\) ,却与一般的 \(DP\) 题不同。能够看出是两个相邻区间合并,但是却不知道具体是哪两个区间。

因此,我们需要将区间加入状态描述中。左端点,区间长度,右端点三选二。这里选择左端点和区间长度。

设 \(dp_{i,j}\) 表示以 \(j\) 为左端点合成数字 \(i\) 的区间长度。当区间长度为 \(0\) 时,表示不存在这样的区间。

则可得到状态转移方程:

\(dp[i][j]=dp[i-1][j]+dp[i-1][j+dp[i-1][j]]\)

code

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,dp[60][270000],ans;
int main(){
	scanf("%d",&n);
	int x;
	for(int i=1;i<=n;i++) scanf("%d",&x),dp[x][i]=1;
	for(int i=2;i<=58;i++){
		for(int j=1;j<=n;j++){
			if(!dp[i][j]) 
				if(dp[i-1][j]&&dp[i-1][j+dp[i-1][j]])//判断两个区间是否存在 
					dp[i][j]=dp[i-1][j]+dp[i-1][j+dp[i-1][j]];
			if(dp[i][j]) ans=max(ans,i);
		}
	} 
	cout<<ans<<endl;
	return 0;
}

\(i\) 的最大值为 \(58\) 是因为 \(2^{18}=262144\) 且范围为 \(1\sim40\)。

所以 \(i\) 的最大值为 \(40+18=58\)。

summary

算是拓宽了在区间 \(dp\) 解法中的另一种常规思路吧。和 \(ST\) 算法有着异曲同工之妙,也算变相复习了 \(ST\) 算法了。

\(2023.1.29\)

标签:状态,纪念品,int,做题,DP,include,合集,dp
From: https://www.cnblogs.com/lzyan-blog/p/17071592.html

相关文章

  • Wordpress后台网址安全
    wordpress固定的后台地址是网站/wp-admin/如果对方知道你是wp建站,然后很自然的就能知道你后台登录地址。然而你密码简单的话,很容易被黑。所以为了安全考虑,我们需要把这......
  • Wordpress主题twentytwelve修改首页文章摘要
    方法:网站后台->外观->编辑->找到content.php文件路径:wp-content/themes/twentytwelve/找到这一句:<?phpif(is_search())://Onlydisplayexcerptsforsearch.?......
  • Wordpress指定关键词手动添加链接
    方法:网站后台->外观->编辑->找到functions.php文件wp-content/themes/当前外观/functions.php在当前外观的functions.php末尾中添加以下代码:/**文章关键词指定链接......
  • 背包DP
    背包dp前言:由于普通的背包板子太板了,所以不多赘述,直接讲有价值的1.多重背包的二进制优化把一个物品的数量二进制拆分,例如有10个价值a的物品,我们把它拆成1+2+4+3个,这样......
  • 提高程序员工作效率的工具合集windows+ios
    提示:集合各种程序员必备工具,望学习收藏~文章目录​​前言​​​​一、Markdowm​​​​1:菜单栏​​​​2:文件​​​​3:编辑​​​​4:段落​​​​5:格式​​​​6:视图​​​......
  • 什么是DPT中的Odd Cycle问题?它会有什么问题?该如何解决?
    什么是DPT中的OddCycle问题?它会有什么问题?该如何解决?本文选自知识星球中的ICC2教程,更多IC干货见星球,同时星球QQ群还有分享高达40多万字的个人数字后端设计笔记,欢迎加入,......
  • 对 sosdp 的一些理解
    sosdp可以做的题目:对子集/超集的dp,这里对子集相关的部分做一下分析参考资料设\(f[mask][i]\)表示从低到高考虑到\(mask\)的第\(i\)位(从0开始算),而且这\(i+1\)......
  • 【面试高频题】难度 3.5/5,综合最短路的 DP 问题
    题目描述这是LeetCode上的​​1976.到达目的地的方案数​​,难度为中等。Tag:「最短路」、「拓扑排序」、「动态规划」你在一个城市里,城市由 个路口组成,路口编号为......
  • 算法_dp
    2023牛客寒假算法基础集训营1B题四维dp+前缀和处理题目描述众所周知,2022年是四年一度的世界杯年,那么当然要整点足球题。本题需要你模拟一支队伍的一赛季联赛征程。联......
  • 状压 DP(ZR)
    [PKUSC2018]最大前缀和从部分分出发考察性质,“满足a中至多一个负数”怎么做?好吧这个很简单,但是它提醒我们从负数的POV考虑。不难发现,最大前缀和的结束为止一定是某个......