复兴提高DAY04区间动态规划
2025-07-04 23:40:34
发布于：上海
22阅读
0回复
0点赞
T1【区间动态规划】石子合并问题I
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 310, INF = 0x3f3f3f3f;
// dp[i][j] 定义状态从第 i 堆到第 j 堆的最小得分
// a 数组记录每堆石子数目, sum 前缀和数组
int dp[MAXN][MAXN], n, a[MAXN], sum[MAXN];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum[i] = sum[i - 1] + a[i]; // 前缀和
}
// 自底向上dp，L 代表区间长度
for (int L = 2; L <= n; L++)
{
// i-左端点的下标，j-右端点的下标，将所有区间组合的石子堆枚举
for (int i = 1, j = L; j <= n; i++, j++)
{
dp[i][j] = INF; // 这个子区间合成的石子堆dp[i][j]得分赋值无穷大
for (int k = i; k < j; k++) // 枚举 k 的值 [i, j)
{
int next = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
dp[i][j] = min(dp[i][j], next);
}
}
}
cout << dp[1][n];
return 0;
}
T2【区间动态规划】石子合并问题II
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 610, INF = 0x3f3f3f3f;
// dp[i][j] 定义状态从第 i 堆到第 j 堆的最小得分
// a 数组记录每堆石子数目, sum 前缀和数组
int dp[MAXN][MAXN], n, a[MAXN], sum[MAXN];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum[i] = sum[i - 1] + a[i]; // 前缀和
}
// 处理另一半
for (int i = 1; i <= n; i++)
{
a[n + i] = a[i];
sum[n + i] = sum[n + i - 1] + a[n + i];
}
// 自底向上dp，L代表区间长度
for (int L = 2; L <= n; L++)
{
// i-左端点的下标，j-右端点的下标，将所有区间组合的石子堆枚举
for (int i = 1, j = L; j <= (n << 1); i++, j++)
{
dp[i][j] = INF; // 这个子区间合成的石子堆dp[i][j]得分赋值无穷大
for (int k = i; k < j; k++) // 枚举 k 的值 [i, j)
{
int next = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
dp[i][j] = min(dp[i][j], next);
}
}
}
int mini = INF;
for (int i = 1; i <= n; i++)
{
mini = min(mini, dp[i][i + n - 1]);
}
cout << mini;
return 0;
}
T3【区间动态规划】能量项链
#include<bits/stdc++.h>
using namespace std;
int n,head[209],tail[209];
int f[209][209];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> head[i]; //头坐标
if(i!=1)
tail[i-1]=head[i]; //当前珠子的头是上一个珠子的尾
}
tail[n]=head[1];
for(int i=1;i<=n;i++)
{
head[i+n]=head[i];
tail[i+n]=tail[i];
}
for(int len = 1; len <= n; len++) //枚举长度
{
for(int i = 1; i + len-1 <= 2 * n; i++) // 左端点
{
int j = len + i - 1; //右端点
for(int k = i ; k < j ; k++) //在i~j中 挑选一个k将区间分开
f[i][j] = max(f[i][j], f[i][k] + f[k+1][j] + head[i]*head[k+1]*tail[j]);
}
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,f[i][n+i-1]);
cout << res;
return 0;
}
T4【区间动态规划】回文子串
#include<bits/stdc++.h>
using namespace std;
int n,dp[1010][1010]; //dp[i][j]:两个字符串分别以i和j结尾，最长公共子序列的长度
char str1[1010],str2[1010];
int main()
{
scanf("%s",str1+1);
int len=strlen(str1+1);
for(int i=1;i<=len;i++)
str2[i]=str1[len-i+1];
for(int i=1;i<=len;i++)
{
for(int j=1;j<=len;j++)
{
if(str1[i]==str2[j])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
printf("%d\n",len-dp[len][len]);
return 0;
}
这里空空如也
有帮助，赞一个