目前进度——动态规划1：线性dp、背包问题，区间
好题
1026 合并回文子串
标签
区间 DP
引入——经典问题，最长回文字串
- 问题：给定字符串 \(S\)，求 \(S\) 的最长回文字串的长度。
- 思路：因为长回文串都可通过小回文串在两端添加相同字符得到，故设 \(dp_{i,j}\) 表示字串 \(S_{i,\dots,j}\) 是否回文，则当 \(S_i=S_j\) 时，有 \(dp_{i,j}|=dp_{i+1,j-1}\)。特殊地，对长度为 \(1\) 和 \(2\) 的字串进行初始化。
本题思路
- 紧承引入，我们可以设 \(dp_{i,j,k,l}\) 表示由 \(A_{i,\dots,j}\) 和 \(B_{k,\dots,l}\) 合并成的字串是否回文。类比求转移方程即可。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
char a[maxn],b[maxn];
int dp[maxn][maxn][maxn][maxn],T;
int ans;
int main()
{
scanf("%d",&T);
int la,lb;
while(T--)
{
ans=0;
cin>>a+1>>b+1;
la=strlen(a+1),lb=strlen(b+1);
memset(dp,0,sizeof(dp));
for(int l=0;l<=la;l++)
{
for(int li=0;li<=lb;li++)
{
for(int i=1;i+l-1<=la;i++)
{
for(int k=1;k+li-1<=lb;k++)
{
int j=i+l-1,p=k+li-1;
if(l+li<=1) dp[i][j][k][p]=1;
else
{
if(a[i]==a[j]) dp[i][j][k][p]|=dp[i+1][j-1][k][p];
if(a[i]==b[p]) dp[i][j][k][p]|=dp[i+1][j][k][p-1];
if(b[k]==b[p]) dp[i][j][k][p]|=dp[i][j][k+1][p-1];
if(a[j]==b[k]) dp[i][j][k][p]|=dp[i][j-1][k+1][p];
}
if(dp[i][j][k][p]) ans=max(ans,l+li);
}
}
}
}
printf("%d\n",ans);
}
return 0;
}
1027 取数游戏2
标签
区间 DP
思路
- 因为序列 A 任意阶段的状态都是由上一阶段对应的状态通过拿走左端或右端的元素转移得到，故可设 \(dp_{l,r}\) 表示从 A 左端取走 \(l\) 个数且从右端取走 \(r\) 个数所能求得的 \(\sum v\) 的最大值。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int t,n,a[maxn],b[maxn],dp[maxn][maxn],ans;
int main()
{
scanf("%d",&t);
while(t--)
{
ans=-1;
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int j=1;j<=n;j++)
scanf("%d",&b[j]);
for(int i=1;i<=n;i++)
{
for(int l=0;l<=i;l++)
{
int r=i-l;
if(l==0) dp[0][r]=dp[0][r-1]+b[i]*a[n-r+1];
if(r==0) dp[l][0]=dp[l-1][0]+b[i]*a[l];
else dp[l][r]=max(dp[l-1][r]+b[i]*a[l],
dp[l][r-1]+b[i]*a[n-r+1]);
ans=max(ans,dp[l][r]);
}
}
printf("%d\n",ans);
}
return 0;
}
1028 wyh的问题
标签
区间 DP
思路
- 因为区间在从路灯 \(i\) 前往路灯 \(j\) 时，会顺手关掉 \(i\) 与 \(j\) 之间的路灯，所以可用区间 DP。设 \(dp_{i,j}\) 表示关掉路灯 \(i,\dots,j\) 所耗费的最小电量，则发现不知如何从 \(dp_{i+1,j}\) 与 \(dp_{i}{j-1}\) 转移。问题出现在，不知从何位置向 \(dp_{i,j}\) 转移。故应设 \(dp_{i,j,0/1}\) 表示关掉路灯 \(i,\dots,j\) 且在左/右段的最小电量，则可转移。
- 发现转移方程中并不是路灯之间的距离，而是路灯之间的位移。这是因为路灯 \(i,\dots,j\) 在位置 D 上不一定属于一个区间（具体来讲，不一定存在一个区间，使得这个区间中只包含路灯 \(i,\dots,j\) 的 \(D\)）。但因为会顺手关掉经过的路灯，故当位移为负时，可认为是在返回本应顺手关了却没关的电量。
代码
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e3+10;
const ll INF=1e16;
int n,v,d[maxn],w[maxn];
ll sumw[maxn],dp[maxn][maxn][2];
int main()
{
while(cin>>n)
{
scanf("%d",&v);
for(int i=1;i<=n;i++)
scanf("%d%d",&d[i],&w[i]),
sumw[i]=sumw[i-1]+w[i];
memset(dp,0x3f3f3f3f,sizeof(dp));
dp[v][v][0]=0,dp[v][v][1]=0;
for(int l=2;l<=n;l++)
{
for(int i=1;i+l-1<=n;i++)
{
int j=i+l-1;
dp[i][j][0]=min(dp[i+1][j][0]+1ll*(d[i+1]-d[i])*(sumw[n]-sumw[j]+sumw[i]),
dp[i+1][j][1]+1ll*(d[j]-d[i])*(sumw[n]-sumw[j]+sumw[i]));
dp[i][j][1]=min(dp[i][j-1][1]+1ll*(d[j]-d[j-1])*(sumw[n]-sumw[j-1]+sumw[i-1]),
dp[i][j-1][0]+1ll*(d[j]-d[i])*(sumw[n]-sumw[j-1]+sumw[i-1]));
}
}
printf("%lld\n",min(dp[1][n][0],dp[1][n][1]));
}
return 0;
}
1029 [NOIP2007]矩阵取数游戏
标签
区间 DP 高精度/Python
建议
- 因为高精度容易打爆且耗费时间，又因为 xcpc 对不同语言的时空要求不同，故可用 Python 平替高精度。
代码
点击查看代码
n,m=[int(e) for e in input().split()]
a=[]
for _ in range(n):
a.append([int(e) for e in input().split()])
ans=0
for i in range(n):
dp=[[0 for _ in range(m)] for _ in range(m)]
for li in range(m-1,0,-1):
for l in range(m-li+1):
r=l+li-1
if l and r==m-1:
dp[l][r]=dp[l-1][r]+a[i][l-1]*2**(m-li)
if l==0 and r<m-1:
dp[l][r]=dp[l][r+1]+a[i][r+1]*2**(m-li)
elif l>0 and r<m-1:
dp[l][r]=max(dp[l][r+1]+a[i][r+1]*2**(m-li),
dp[l-1][r]+a[i][l-1]*2**(m-li))
ans+=max([dp[j][j]+a[i][j]*2**m for j in range(m)])
print(ans)
# for i in range(n):
# dp=[[0 for _ in range(m)] for _ in range(m)]
# for j in range(m):
# dp[j][j]=a[i][j]
# for li in range(2,m+1):
# for l in range(m-li+1):
# r=l+li-1
# dp[l][r]=max(dp[l+1][r]*2+a[i][l],
# dp[l][r-1]*2+a[i][r])
# ans+=dp[0][m-1]
# print(ans*2)
1032 迁徙过程中的河流
标签
贪心 排序 与次序有关的线性 DP
思路
- 根据贪心，让两个用时长的人划船到彼岸，让用时短的人划船回到此岸均有可能使得总用时变短。
- 因为话划船时间由慢的决定，故耗时多的是不可避免地会对总用时造成贡献，故可对 \(T\) 进行重排，使得 \(T_1\le T_2\dots\le T_n\)。根据 1，可得到两种使得此岸序列变为 \(T_1，T_2,\dots,T_{n-2}\) 的方法：第一种，首先让 1 和 2 到彼岸，再让 1 划船回来，再让 n-1 与 n 划过去，最后让 2 划回此岸；第二种，让 1 把 n 运过去，再回来把 n-1 过去。可以证明，没有其他方案比这两种更优。故可递推求解。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,a[maxn],dp[maxn];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
dp[1]=a[1],dp[2]=a[2];
dp[3]=a[1]+a[2]+a[3];
for(int i=4;i<=n;i++)
dp[i]=min(dp[i-2]+2*a[1]+a[i-1]+a[i],
dp[i-2]+2*a[2]+a[1]+a[i]);
printf("%d",dp[n]);
}
1033 小A的回文串
标签
区间 DP 字符串
思路
- 借鉴 1030 石子合并 ，可以在字符串后面再接一遍。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
char a[maxn<<1];
int dp[maxn<<1][maxn<<1],ans=1;
int main()
{
cin>>a+1;
int n=strlen(a+1);
for(int i=1;i<=n;i++)
a[n+i]=a[i];
for(int i=1;i<2*n;i++)
dp[i][i]=1;
for(int i=1;i<2*n-1;i++)
if(a[i]==a[i+1]) dp[i][i+1]=1;
for(int li=3;li<=n;li++)
{
for(int l=1;li+l-1<=2*n-1;l++)
{
int r=l+li-1;
if(a[l]==a[r]) dp[l][r]|=dp[l+1][r-1];
if(dp[l][r]) ans=max(r-l+1,ans);
}
}
printf("%d",ans);
}
1035 简单瞎搞题
bitset 介绍
思路
- bitset 优化时间，滚动数组优化空间。
- 时间复杂度为 \(\mathcal O(\frac{10^6n(R-L)}{w})\)，其中 \(w=32\)。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+1;
bitset<maxn>dp[2],zero;
int n,l[105],r[105];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&l[i],&r[i]);
for(int x=l[1];x<=r[1];x++)
dp[0][x*x]=1;
for(int i=2;i<=n;i++)
{
for(int x=l[i];x<=r[i];x++)
dp[1]|=dp[0]<<(x*x);
dp[0]=dp[1],dp[1]=zero;
}
printf("%d",dp[0].count());
return 0;
}