【动态规划3】区间与环形动态规划

题单链接：【动态规划3】区间与环形动态规划 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

---

P1435 [IOI2000] 回文字串 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题还有另外一种做法，利用LCS求解，可以看另外一篇文章：【动态规划2】线性状态动态规划 | Heavenhold。

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int dp[1010][1010];
//有两种做法 一种是最长上升子序列 在另外一篇文章讲了
//这里介绍区间dp的做法
//dp[i][j] 表示要把从i到j的字符串变成回文串需要插入的最少字符数
//状态转移方程
//dp[i][j]=dp[i+1][j-1] id(s[i]==s[j])
//dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1
void solve()
{
    std::string s;  std::cin>>s;
    int len=s.size();
    s='@'+s;
    for(int k=2;k<=len;k++)
    {
        for(int i=1;i<len;i++)
        {
            int j=i+k-1;
            if(s[i]==s[j])  dp[i][j]=dp[i+1][j-1];
            else    dp[i][j]=std::min(dp[i+1][j],dp[i][j-1])+1;
        }
    }
    std::cout<<dp[1][len]<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P1775 石子合并（弱化版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int dp[310][310];
//dp[i][j] 表示将从第i堆到第j堆的所有石子合并需要的最小代价
//状态转移方程
//dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[j]-sum[k]+sum[k]-sum[i-1],dp[i][j]);
//其中k表示的是分段点
int a[310];
int sum[310];
//sum表示的前缀和
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)
    {
        std::cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        dp[i][i]=0;
    }
    for(int k=2;k<=n;k++)
    {
        for(int i=1;i<n;i++)
        {
            int j=i+k-1;
            for(int p=i;p<=j && j<=n ;p++)    //p表示分段点 注意j要<=n 否则可能会越界
            {
                dp[i][j]=std::min(dp[i][j],dp[i][p]+dp[p+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    std::cout<<dp[1][n];
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

Zuma - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int dp[510][510];
//dp[i][j] 表示将从第i堆到第j堆的所有珠子取走需要的最小时间
//状态转移方程
//dp[i][j]=min(dp[i+1][j-1],dp[i][j]) if(a[i]==a[j])
//dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j]);
//wsm会是下面的这个呢 我们分析一下区间DP的原理
//区间DP其实是以某一个区间为中心 往其两边不断添加点或者区间 从而扩展的
//也就是  <---[====]--->
//而通过枚举分段点 我们可以得到每一种情况 取min 从而得到最小的情况 也就是答案
int a[510];
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)
    {
        std::cin>>a[i];

    }
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<n;i++)
    {
        dp[i][i+1]=1+(a[i]!=a[i+1]);
    }
    for(int i=1;i<=n;i++)   dp[i][i]=1;
    for(int k=2;k<=n;k++)
    {
        for(int i=1;i<n;i++)
        {
            int j=i+k-1;
            if(j<=n)
            {
                if(a[i]==a[j] && i+1<=j-1)
                {
                    //注意这里需要取min 因为在两边添加不一定是最优的
                    dp[i][j]=std::min(dp[i+1][j-1],dp[i][j]);
                    //std::cout<<dp[i][j]<<" 1 \n";
                }
                for(int p=i;p<j;p++)
                {
                    dp[i][j]=std::min(dp[i][j],dp[i][p]+dp[p+1][j]);
                    //std::cout<<dp[i][j]<<" 2 \n";
                }
            }

        }
    }
    std::cout<<dp[1][n]<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P3205 [HNOI2010] 合唱队 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int dp[1010][1010][2];
//dp[i][j][opt] 表示从第i个位置到第j个位置之间 最后一个人是从左边/右边插入的方案数
//0 表示从左边插入 1 表示从右边插入
//根据题意 我们不难得出状态转移方程
/*
if(a[i]<a[i+1])     dp[i][j][0]+=dp[i+1][j][0];
if(a[i]<a[j])   dp[i][j][0]+=dp[i+1][j][1];
if(a[j]>a[j-1])     dp[i][j][1]+=dp[i][j-1][1];
if(a[i]<a[j])   dp[i][j][1]+=dp[i][j-1][0];
 */
//考虑初始化 dp[i][i][0]=1 我们默认一开始是从左边插入
int a[1010];
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)   std::cin>>a[i];
    for(int i=1;i<=n;i++)   dp[i][i][0]=1;
    for(int k=2;k<=n;k++)
    {
        for(int i=1;i<n;i++)
        {
            int j=i+k-1;
            if(j<=n)
            {
                if(a[i]<a[i+1])     dp[i][j][0]+=dp[i+1][j][0];
                if(a[i]<a[j])   dp[i][j][0]+=dp[i+1][j][1];
                if(a[j]>a[j-1])     dp[i][j][1]+=dp[i][j-1][1];
                if(a[i]<a[j])   dp[i][j][1]+=dp[i][j-1][0];
                dp[i][j][0]%=mod;
                dp[i][j][1]%=mod;
            }
        }
    }
    std::cout<<(dp[1][n][0]+dp[1][n][1])%mod;
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P4170 [CQOI2007] 涂色 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int dp[55][55];
//dp[i][j] 表示从第i个位置到第j个位置需要的操作次数
//状态转移方程
//if(s[i]==s[j])  dp[i][j]=std::min(dp[i+1][j],dp[i][j-1]);
//原来一开始还加了一个 dp[i+1][j-1] 
//也就是：dp[i][j]=std::min(dp[i+1][j],dp[i][j-1],dp[i+1][j-1]);
//但是这个是不对的 其实很显然 如果需要添加一种新的颜色 那么就需要加1了
//但是如果这样问题就很麻烦了 我们还得记录出现的颜色种类 其实上面的状态转移方程已经一步步转移过来了
//不再需要考虑这种特别复杂的情况
void solve()
{
    std::string s;  std::cin>>s;
    int n=s.size();
    s='@'+s;
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)   dp[i][i]=1;
    for(int k=2;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            int j=i+k-1;
            if(j>n)   break;
            if(s[i]==s[j])  dp[i][j]=std::min(dp[i+1][j],dp[i][j-1]);
            for(int p=i;p<j;p++)
            {
                dp[i][j]=std::min(dp[i][j],dp[i][p]+dp[p+1][j]);
            }
        }
    }
    std::cout<<dp[1][n]<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P1063 [NOIP2006 提高组] 能量项链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int dp[210][210];
//dp[i][j] 表示从第i个位置到第j个位置 可以释放的最多能量
//区间dp 因为涉及到环 所以拆环成链 具体是a[i+n]=a[i]这一步操作
//注意最长的长度是n 所以k的枚举范围是2-n 并且j<=2*n
//注意枚举分段点时 p是从i开始的 一开始我也是从i开始 后来改成从i+1开始 样例就错了
//确实是得从i开始 因为1个两珠子的串是可能从2个珠子合成的
//这里一开始是打算开一个结构体 记录头标记 尾标记 其实没必要 因为首位相连 所以直接取下一个珠子的头标记即可
//注意最后获取答案 长度是n
int a[210];
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)   std::cin>>a[i],a[i+n]=a[i];
    int ans=0;
    for(int k=2;k<=n;k++)
    {
        for(int i=1;i+k-1<=2*n;i++)
        {
            int j=i+k-1;
            //if(j>2*n)   std::cout<<j<<"\n";
            for(int p=i;p<j;p++)
            {
                dp[i][j]=std::max(dp[i][j],dp[i][p]+dp[p+1][j]+a[i]*a[p+1]*a[j+1]);
                //if(p>2*n)   std::cout<<p<<"\n";
            }
        }
    }
    for(int i=1;i<=n;i++)   ans=std::max(ans,dp[i][i+n-1]);
    std::cout<<ans;
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P1880 [NOI1995] 石子合并 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int dp1[210][210];  //最大得分
int dp2[210][210];  //最小得分
int a[210];
int sum[210];
//要被自己的sb错误笑死了 一直把k当作枚举点 这已经是第二次了
//还是相同的方法 环拆成链 枚举断点
//需要预处理出前缀和
//注意单独一个堆是不能合成的 所以它的得分是0
//最后答案取长度为n的区间
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)
    {
        std::cin>>a[i];
        a[i+n]=a[i];
    }
    for(int i=1;i<=2*n;i++)
    {
        sum[i]=sum[i-1]+a[i];
    }
    memset(dp2,0x3f,sizeof(dp2));
    for(int i=1;i<=2*n;i++)     dp2[i][i]=0;
    for(int k=2;k<=n;k++)
    {
        for(int i=1;i+k-1<=2*n;i++)
        {
            int j=i+k-1;
            for(int p=i;p<j;p++)
            {
                dp1[i][j]=std::max(dp1[i][j],dp1[i][p]+dp1[p+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    for(int k=2;k<=n;k++)
    {
        for(int i=1;i+k-1<=2*n;i++)
        {
            int j=i+k-1;
            for(int p=i;p<j;p++)
            {
                dp2[i][j]=std::min(dp2[i][j],dp2[i][p]+dp2[p+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    int maxAns=0;
    int minAns=1e9;
    for(int i=1;i<=n;i++)
    {
        maxAns=std::max(maxAns,dp1[i][i+n-1]);
        minAns=std::min(minAns,dp2[i][i+n-1]);
    }
    std::cout<<minAns<<"\n"<<maxAns;
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}