6 区间DP

目录

1 石子合并

 2 环形石子合并

3 能量项链

4 凸多边形的划分

5 加分二叉树 

6 棋盘分割（记忆化搜索+二维前缀和）

1 石子合并

282. 石子合并 - AcWing题库

#include
using namespace std;
const int N=310;
int s[N],f[N][N];//s是前缀和
int main()
{
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
      cin>>s[i];
      s[i]+=s[i-1];//求一遍前缀和
  }
  for(int len=2;len<=n;len++)//枚举l到r之间的长度
    for(int l=1;l+len-1<=n;l++)//枚举l
    {
      int r=l+len-1;//根据长度和l获得r
      f[l][r]=0x3f3f3f3f;//因为更新最小值，则把该数定义成最大值
      for(int k=l;k 
 
 2 环形石子合并 
 
枚举环形，我们都可以拉伸成线性，数量由n->2n
 
 
 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
线形石子合并跟上面的状态分析一样，只不过多开个g来存最大值
 
#include
using namespace std;
const int N=410;
int s[N],f[N][N],g[N][N];//s是前缀和，f记录最小值，g记录最大值
int main()
{
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
      cin>>s[i];
      s[n+i]=s[i];//复制后面的重复的一段
  }
  for(int i=1;i<=2*n;i++) s[i]+=s[i-1];//求一遍前缀和
  for(int len=2;len<=n;len++)//枚举l到r之间的长度
    for(int l=1;l+len-1<=2*n;l++)//枚举2n个数，也就是还变成线形的数
    {
      int r=l+len-1;//根据长度和l获得r
      f[l][r]=0x3f3f3f3f;//因为更新最小值，则把该数定义成最大值
      g[l][r]=-0x3f3f3f3f;//因为更新最大值，则把该数定义成最小值
      for(int k=l;k 
 
3 能量项链 
 
因为这里也是环形跟上一题一样要进行拉伸成线形
 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
 
 
#include
using namespace std;
const int N=210;
int w[N],f[N][N];
int main()
{
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
      cin>>w[i];
      w[n+i]=w[i];//因为是环形，转化成线形
  }
  for(int len=3;len<=n+1;len++)//枚举l到r的长度
    for(int l=1;l+len-1<=2*n;l++)
    {
        int r=len+l-1;
        f[l][r]=-0x3f3f3f3f;//因为要求最大值，所以初始化为负无穷
        for(int k=l+1;k 
 
 
4 凸多边形的划分 
 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
 
 由于这题每个w[i]都是10^9，则三个乘以的话就10^27，则要自己写个高精度加法与乘法
 
状态分析跟上一题一样
 
//没加高精度的模板，过不了
#include
using namespace std;
const int N=210;
int w[N],f[N][N];
int main()
{
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)  cin>>w[i];
  for(int len=3;len<=n;len++)//枚举l到r的长度
    for(int l=1;l+len-1<=n;l++)
    {
        int r=len+l-1;
        f[l][r]=0x3f3f3f3f;//因为要求最小值，所以初始化为正无穷
        for(int k=l+1;k 
 AC加了高精度
 
#include
using namespace std;
typedef long long ll;
const int N=55,M=35;
ll w[N],f[N][N][M];
void add(ll a[],ll b[])//高精度加法
{
    static ll c[M];
    memset(c,0,sizeof c);
    ll t=0;
    for(int i=0;i=0;i--)
        if(a[i]>b[i]) return true;
        else if(a[i]=0) cout<>n;
  for(int i=1;i<=n;i++)  cin>>w[i];
  ll temp[M];
  for(int len=3;len<=n;len++)//枚举l到r的长度
    for(int l=1;l+len-1<=n;l++)
    {
        int r=len+l-1;
        //f[l][r]=0x3f3f3f3f;
        f[l][r][M-1]=1;//因为要求最小值，所以初始化为正无穷，最高位是1，说明1e34,已经很大了
        for(int k=l+1;k 
 
 
5 加分二叉树  
 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
 
输出时是要求前序遍历，则递归输出根左右
 
 
#include
using namespace std;
typedef long long ll;
const int N=35;
int w[N],f[N][N],g[N][N];//f记录[l,r]区间的分数，g记录[l,r]的根节点
void dfs(int l,int r)//前序遍历是根左右
{
    if(l>r) return ;
    int root=g[l][r];//根
    cout<>n;
   for(int i=1;i<=n;i++) cin>>w[i];
   memset(f,-0x3f,sizeof f);//因为要求最大值，则初始化为负无穷
   for(int len=1;len<=n;len++)//枚举[l,r]的长度
     for(int l=1;l+len-1<=n;l++)//枚举l
     {
         int r=l+len-1;
         if(len==1) f[l][r]=w[l],g[l][r]=l;//假如只有自己，则分数是自己，根也是自己
         else
         {
             for(int k=l;k<=r;k++)//枚举[l,r]之间的根节点
             {
                 int left=k==l?1:f[l][k-1];//假如k是等于l，说明l到k没有左子树，则分数为1
                 int right=k==r?1:f[k+1][r];//假如k是等于r，说明l到k没有右子树，则分数为1
                 int socre=left*right+w[k];//算一下分数
                 if(f[l][r] 
 
 
6 棋盘分割（记忆化搜索+二维前缀和） 
 
321. 棋盘分割 - AcWing题库
 
 
 
#include
using namespace std;
typedef long long ll;
const int N=15,M=9;
const double INF=1e9;
int s[M][M];//二维前缀和
double f[M][M][M][M][N];
double X;//平均数
int n;
double get(int x1,int y1,int x2,int y2)//求子矩阵的方差
{
    double sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]-X;//求方差
    return sum*sum/n;
}
double dp(int x1,int y1,int x2,int y2,int k)//记忆化搜索
{
    double &v=f[x1][y1][x2][y2][k];
    if(v>=0) return v;//假如已经处理过直接返回他的值
    if(k==1) return v=get(x1,y1,x2,y2);//假如切割是一次，则就是最后一块子矩阵，则直接求他的值，不用再切割
    v=INF;//因为要求最小值，初始化为正无穷
    for(int i=x1;i>n;
   for(int i=1;i<=8;i++)
     for(int j=1;j<=8;j++)
     {
        cin>>s[i][j];
        s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];//二维前缀和
     }
    memset(f,-1,sizeof f);//初始化为-1，便于记忆化搜索
    X=(double)s[8][8]/n;//求平均数
    printf("%.3lfn",sqrt(dp(1,1,8,8,n)));//输出根号方差，即均方差
    return 0;
}