动态规划区间DP

动态规划区间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;
}