动态规划区间DP_C/C++

动态规划区间dp

普通区间dp

在这里插入图片描述

石子合并(蓝桥官网1233)

请添加图片描述

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int n=300;
int n,a[n],s[n],f[n][n];
signed main(){
    cin>>n;
    memset(f,127,sizeof(f));//初始化f为较大值
    for(int i=1;i<=n;i++){
      cin>>a[i];
      f[i][i]=0;//长度为1的区间不用合并，代价0
      s[i]=s[i-1]+a[i];//前缀和sum(i,j)
    }
    for(int len=2;len<=n;len++)
      for(int i=1;i+len-1<=n;i++){
        int j=i+len-1;
        for(int k=i;k<j;k++){
          f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
        }
      }
    cout<<f[1][n];
}

涂色(蓝桥官网926)

在这里插入图片描述

请添加图片描述

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int n=60;
int f[n][n];
signed main(){
    string s;cin>>s;
    int n=s.size();
    memset(f,127,sizeof(f));
    for(int i=0;i<n;i++)f[i][i]=1;

    for(int len=2;len<=n;len++)
      for(int i=0;i+len-1<n;i++){
        int j=i+len-1;
        if(s[i]==s[j])//两端颜色相同
          f[i][j]=min(f[i+1][j],f[i][j-1]);
        else{//区间dp
          for(int k=i;k<j;k++)
          f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
        }
      }
      cout<<f[0][n-1];
}

制作回文串(蓝桥官网1547)

在这里插入图片描述

请添加图片描述

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int n=2e3+9;
string s;
int n,m,w1[30],w2[30],f[n][n];
signed main(){
  cin>>m>>n>>s;
  for(int i=1;i<=m;i++){
    char ch;cin>>ch;
    cin>>w1[ch-'a']>>w2[ch-'a'];
  }
  for(int len=2;len<=n;len++)
    for(int i=0;i+len-1<n;i++){
      int j=i+len-1;
      if(s[i]==s[j]){//左右同色
        if(len==2) f[i][j]==0;
        else f[i][j]=f[i+1][j-1];
      }
      else //区间dp
      f[i][j]=min(f[i+1][j]+min(w1[s[i]-'a'],w2[s[i]-'a']),
                  f[i][j-1]+min(w1[s[j]-'a'],w2[s[j]-'a']));
    }
    cout<<f[0][n-1];
}

环形区间dp

在这里插入图片描述

能量项链(蓝桥官网557)

请添加图片描述

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int n=209;
int n,a[n*2],dp[n*2][n*2];
signed main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    a[n+i]=a[i];//环形区间dp,复制
  }
  for(int len=2;len<=n;len++)
  for(int i=1;i+len-1<=n*2;i++){
      int j=i+len-1;
      for(int k=i;k<j;k++)
      dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1]);
  }
  int ans=0;
  for(int i=1;i<=n;i++)
  ans=max(ans,dp[i][i+n-1]);
  cout<<ans;
}