区间dp学习5——hdu 5115——Dire Wolf——做题反思-白红宇的个人博客

区间dp学习5——hdu 5115——Dire Wolf——做题反思

发布日期：2021-05-07 03:07:43 浏览次数：20 分类：精选文章

本文共 2187 字，大约阅读时间需要 7 分钟。

这个题令我对区间dp有了新的理解，很满足能够在做题慢的情况下能够对题目所涉及的知识最大程度掌握

前面的分析过程我学到了很多，还有一个学习到的点是边界区间枚举，这是区间dp第二种表达方式经常需要处理的点

对应的网上代码（主要实现部分）

memset(dp,INF,sizeof(dp));        for(int i=1;i<=n;i++)            dp[i][i]=a[i]+b[i-1]+b[i+1];///区间长度为1的时候的情况        for(int len=2;len<=n;len++)///枚举所有可能的区间长度        {               for(int i=1;i<=n-len+1;i++)///枚举所有可能的起点            {                   int j=i+len-1;///j代表区间的右端点///即区间[i,j]                dp[i][j]=min(dp[i+1][j]+a[i]+b[i-1]+b[j+1],dp[i][j-1]+a[j]+b[i-1]+b[j+1]);///先考虑左右端点时候的特殊情况                for(int k=i+1;k

但我后来反思了，其实这里可以简化（先看图片解释的思路，再看代码）：

memset(dp, 0, sizeof(dp));	for (int i = 1; i <= n; i++)		dp[i][i] = a[i] + b[i - 1] + b[i + 1];//2.初始化用到了区间化思想（区间dp）	for (int len = 1; len < n; len++)	{   		for (int i = 1; i + len <= n; i++)		{   			int j = i + len;			//dp[i][j] = min(dp[i + 1][j] + a[i] + b[i - 1] + b[j + 1], dp[i][j - 1] + a[j] + b[i - 1] + b[j + 1]);//3.边界条件的处理			dp[i][j] = inf;			for (int k = i; k <= j; k++)			{   				dp[i][j] = min(dp[i][k - 1] + dp[k + 1][j] + a[k] + b[i - 1] + b[j + 1], dp[i][j]);			}		}	}

全代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int N = 300;const int inf = 0x3f3f3f3f;int n;int  a[N];int  b[N];int solve();int dp[N][N];int main(){   	int t = 1;	int T;	cin >> T;	while (T--)	{   		cin >> n;		for (int i = 1; i <= n; i++)			cin >> a[i];		for (int i = 1; i <= n; i++)			cin >> b[i];		cout << "Case #" << t++ << ": " << solve() << endl;	}}int solve(){   	a[0] = b[0] = a[n + 1] = b[n + 1] = 0;//1.边界条件的初始化	memset(dp, 0, sizeof(dp));	for (int i = 1; i <= n; i++)		dp[i][i] = a[i] + b[i - 1] + b[i + 1];//2.初始化用到了区间化思想（区间dp）	for (int len = 1; len < n; len++)	{   		for (int i = 1; i + len <= n; i++)		{   			int j = i + len;			//dp[i][j] = min(dp[i + 1][j] + a[i] + b[i - 1] + b[j + 1], dp[i][j - 1] + a[j] + b[i - 1] + b[j + 1]);//3.边界条件的处理			dp[i][j] = inf;			for (int k = i; k <= j; k++)			{   				dp[i][j] = min(dp[i][k - 1] + dp[k + 1][j] + a[k] + b[i - 1] + b[j + 1], dp[i][j]);			}		}	}	return dp[1][n];}

这个题目使我对区间dp第二种表达方式有了一定的理解，在这里归纳一下

1.区间联立性：要考虑区间之间的联系，不能独立化考虑
2.边界条件处理的两种方式以及优先级，以融入区间转移方程为主
3.区间边界状态处理：利用无效区间以及k的分割点枚举

上一篇：第八周学习总结——区间dp的学习

下一篇：区间dp学习4——poj 1651 Multiplication Puzzle——题后反思

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章