区间dp学习2——打表、四边形优化区间枚举（四边形区间优化学习1）-白红宇的个人博客

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

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

区间dp有两种表示方式，这两种方式打出的表格完全一致，但在顺序上有所不同，在这里用回文串题进行说明（这个题目之前有我的分析、题解，是我反思的挺久的一篇文章，可以先看那个再看打表，可能会更清晰，在这篇文章中不会细讲）

对应的打表顺序图示1

在网上还看到其它的区间枚举方式，比如说这种（大概的模板）

for(int i=n-2;i>=0;i--){              for(int j=i+1;j

对应的打表顺序图示2（不细讲了，懂第一种第二种也很好懂的，实际做题时选择一种自己习惯的就好）

还有四边形优化，对于区间dp还挺常用的，学了差不多有一上午的时间了，深知它不是短时间内能学会的，慢慢来吧

目前学习知道了一点，知道这一点也能够将k的枚举量表示出来了（具体证明还不知道，慢慢来吧）

这一点我打了几个石子合并题目的表表来加深对k的枚举范围理解（+对应代码）

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define inf  0x3f3f3f3fusing namespace std;const int N = 300;int n;int cost[N];int dp[N][N];int optk[N][N];int solve();void print_optk();int main(){   	while (cin >> n)	{   		for (int i = 1; i <= n; i++)		{   			int x;			cin >> x;			cost[i] = cost[i - 1] + x;		}		cout << solve() << endl;		for (int i = 1; i <= n; i++)optk[i][i] = i;		print_optk();	}	}int solve(){   	for (int len = 1; len < n; len++)	{   		for (int i = 1; i <= n; i++)		{   			int j = i + len;			dp[i][j] = inf;			/*for (int k = i; k < j; k++)			{				dp[i][j] = min(dp[i][k] + dp[k + 1][j] + cost[j] - cost[i - 1], dp[i][j]);			}*/			for (int k = i; k < j; k++)			{   				if (dp[i][k] + dp[k + 1][j] + cost[j] - cost[i - 1] < dp[i][j])				{   					dp[i][j] = dp[i][k] + dp[k + 1][j] + cost[j] - cost[i - 1];					optk[i][j] = k;				}			}		}	}	return dp[1][n];}void print_optk(){   	for (int i = 1; i <= n; i++)	{   		for (int j = 1; j <= n; j++)			cout << optk[i][j] << " ";		cout << endl;	}}

在这里插入图片描述

对于每一点的状态决定，k值范围总是在[s（i,j-1）-s(i+1,j)]之间

上一篇：区间dp学习3——括号匹配 ——做题反思

下一篇：区间dp学习1——回文串（poj 3208）题后反思

发表评论

关于作者

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

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章