初学DP(3) – 区间性DP & 环形DP – Codevs 1048 石子归并 & NOIP 2006 提高 能量项链

石子归并

题目


题目链接: [http://codevs.cn/problem/1048/
这个看过去一眼仿佛看到了dfs,当然你剪枝得当也许能用 dfs A了, 但是你要是有那个脑子能想出剪枝发我不信你想不出这个DP 我们来想一下如何划分子问题,我们可以十分简单的知道任意两堆合并出来得和是 a[i]+a[i+1] 那么从 a[i] 到 a[i+2] 的距离应当就有三种可能:
a[i] 与 a[i+1]+a[i+2] 合并 a[i]+a[i+1] 与 a[i+2] 合并
然后我们就发现中间实际上 室友一个断点的,我们通过断点找到左区间以及右区间然后合并,最后通过移动断点以找到当前部分的最优解 所以可以得到状态转移方程:
f [ j ] [ j + i ] = max ( f [ j ] [ j + 1 ] , f [ j ] [ k ] + f [ k + 1 ] [ j + i ] + sum [ j + i ] – sum [ j – 1 ] )

代码


#include <cstdio>
#include <cstring>
using namespace std;
int n;
int a[110],sum[110];
int f[110][110];
int main(){
    memset(f,0x7f,sizeof(f));
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
        f[i][i+1]=a[i]+a[i+1];
        f[i][i]=0;
    }
    for(int i=2;i<n;i++){//区间长度
        for(int j=1;j<=n-i;j++){//起点
            for(int k=j;k<j+i;k++){// 断点
                if(f[j][k]+f[k+1][j+i]+sum[j+i]-sum[j-1]<f[j][j+i])
                    f[j][j+i]=f[j][k]+f[k+1][j+i]+sum[j+i]-sum[j-1];
            }
        }
    }
    printf("%d",f[1][n]);
}
其中 f[i][j] 表示从 i 到 j 的代价 sum[i] 表示从 1 到 a[i] 的和

能量项链

题目


题目链接: [http://codevs.cn/problem/1154/]
定睛一看,这tm不就是上面那到题目吗? 不过这个项链是一个圈,并不是一个数列qwq 所以我们要求其进行优化,很显然,我们只需要吧原来的输入再在原来的数组后面接上一遍,然后照样该咋搜咋搜

代码


#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,cnt;
int f[1000][1000],a[11000],sum[1100];
int main(){
    memset(f,0,sizeof(f));
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[i+n]=a[i];//接至数列尾部
    }
    for(int i = 1 ; i < n ; i++){// i 枚举 l
        for(int j = 1,l=i+2 ; l <= 2*n ;j++,l++){// j 一个珍珠的开头 l 另一个珍珠的结尾 
            for(int k = j+1; k < l ; k++){// k 枚举重复项
                f[j][l] = max(f[j][k]+f[k][l]+a[j]*a[k]*a[l],f[j][l]);
            }
        }
    }
    int max=0;
    for(int i=1;i<=n;i++) if(f[i][i+n]>max) max=f[i][i+n];
    printf("%d",max);
}
f [ i ] [ j ] – 珍珠 i 到 j 的最大值

END

环形DP需要我们对数据的环展开成列让后按需求DP 区间性DP通过找到区间,然后合并并比较来进行DP 如果右不理解的,拿代码调调,一定要记住,无论如何都要自己去打上一遍 ]]>

发表评论

电子邮件地址不会被公开。 必填项已用*标注