codeforces/1312E(区间dp)

题目

这道题不管从内容还是数据范围看起来都像是区间dp,可一时想不出来怎么构造出一个满足无后效性的区间状态,看了一眼题解才顿悟。

分两步走,第一步我们求出所有的dp[l][r],表示[l,r]区间可以最终转化为的一个数,如果无法转化则为零,这一步的巧妙就在于包含了足够的信息来“总结”这个区间。第二步我们用前缀dp,设dp2[i]表示前i个元素最少合并为几个点,容易求出。

#include<bits/stdc++.h>
using namespace std;

const int maxn=501;

int dp[maxn][maxn];
int n;
int a[maxn];
int dp2[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],dp[i][i]=a[i];
    for(int len=1;len<=n;len++){
        for(int i=1;i<=n-len+1;i++){
            for(int k=i;k<i+len-1;k++){
                if(dp[i][k]!=0&&dp[i][k]==dp[k+1][i+len-1]){
                    dp[i][i+len-1]=dp[i][k]+1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        dp2[i]=dp2[i-1]+1;
        for(int j=1;j<i;j++){
            if(dp[j][i]>0){
                dp2[i]=min(dp2[i],dp2[j-1]+1);
            }
        }
    }
    printf("%d\n",dp2[n]);
    return 0;
}

反思:在看到数据范围和题目内容后应该坐实区间dp,然后去想怎么样构造出符合无后效性的状态。

全部评论

相关推荐

05-30 18:54
武汉商学院 Java
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
05-12 11:09
已编辑
门头沟学院 后端
已注销:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务