283. 多边形

本文主要是介绍283. 多边形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法分析：
初看起来，就是简单的区间dp，于是很顺利打出来，结果有些点过不了。百思不得其解。下面是初始代码。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n, dotval[110], f[110][110];
char edgval[110];
int main()  // 没有考虑负数，不全面  
{scanf("%d", &n);//使用格式化输入scanf混读%c和%d有点问题，数据不大，可以用cin  for (int i = 1; i <= n; ++i) {cin>>edgval[i]>>dotval[i];edgval[i+n] = edgval[i];dotval[i+n] = dotval[i]; } // 将环拆成链后，每个点前面的那条边是属于该点的边 n *= 2;memset(f, 0xcf, sizeof(f));for (int i = 1; i <= n; ++i)  f[i][i] = dotval[i];for (int len = 2; len <= n; ++len)for (int i = 1; i < n; ++i){int j = i + len - 1;if (j > n) continue;for (int k = i; k < j; ++k){int tem;if (edgval[k+1] == 't') tem = f[i][k] + f[k+1][j];else tem = f[i][k] * f[k+1][j];f[i][j] = max(f[i][j], tem);}}int ans = -1e9;n /= 2;for (int i = 1; i <= n; ++i)if (f[i][i+n-1] > ans) ans = f[i][i+n-1];printf("%d\n", ans);for (int i = 1; i <= n; ++i)if (f[i][i+n-1] == ans) printf("%d ", i);printf("\n");return 0;
}

看书上的讲解，原来是没有考虑负数的问题。状态$f[i][j]$，如果是加号，没有问题。但如果是乘号的话，是不能简单地有$f[i][k]\ast f[k+1][j]$转移过来的。因为两个负数相乘也许是一个超过两个最大值的数。状态$f_{m}ax[i][j]$表示区间$[i,j]$的最大值，$g_{m}in[i][j]$表示最小值。则对于乘号来讲：
$$fmax[i][j]=max(fmax[i][k]\ast fmax[k+1][j],fmax[i][k]\ast gmin[k+1][j],gmin[i][k]\ast fmax[k+1][j],gmin[i][k]\ast gmin[k+1][j])$$
$$gmin[i][j]=min(fmax[i][k]\ast fmax[k+1][j],fmax[i][k]\ast gmin[k+1][j],gmin[i][k]\ast fmax[k+1][j],gmin[i][k]\ast gmin[k+1][j])$$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n, dotval[110], f_max[110][110], g_min[110][110];
char edgval[110];
int main()
{scanf("%d", &n);//使用格式化输入scanf混读%c和%d有点问题，数据不大，可以用cin  for (int i = 1; i <= n; ++i) {cin>>edgval[i]>>dotval[i];edgval[i+n] = edgval[i];dotval[i+n] = dotval[i]; } // 将环拆成链后，每个点前面的那条边是属于该点的边 n *= 2;memset(f_max, 0xcf, sizeof(f_max));  // 极小值 memset(g_min, 0x3f, sizeof(g_min));  // 极大值  for (int i = 1; i <= n; ++i)  f_max[i][i] = g_min[i][i] = dotval[i];for (int len = 2; len <= n; ++len)for (int i = 1; i < n; ++i){int j = i + len - 1;if (j > n) continue;for (int k = i; k < j; ++k){int temmax = -1e9, temmin = 1e9;if (edgval[k+1] == 't'){f_max[i][j] = max(f_max[i][j], f_max[i][k] + f_max[k+1][j]);g_min[i][j] = min(g_min[i][j], g_min[i][k] + g_min[k+1][j]);}else{temmax = max(temmax, f_max[i][k] * f_max[k+1][j]);temmax = max(temmax, f_max[i][k] * g_min[k+1][j]);temmax = max(temmax, g_min[i][k] * f_max[k+1][j]);temmax = max(temmax, g_min[i][k] * g_min[k+1][j]);temmin = min(temmin, f_max[i][k] * f_max[k+1][j]);temmin = min(temmin, f_max[i][k] * g_min[k+1][j]);temmin = min(temmin, g_min[i][k] * f_max[k+1][j]);temmin = min(temmin, g_min[i][k] * g_min[k+1][j]);f_max[i][j] = max(f_max[i][j], temmax);g_min[i][j] = min(g_min[i][j], temmin);}}}int ans = -1e9;n /= 2;for (int i = 1; i <= n; ++i)if (f_max[i][i+n-1] > ans) ans = f_max[i][i+n-1];printf("%d\n", ans);for (int i = 1; i <= n; ++i)if (f_max[i][i+n-1] == ans) printf("%d ", i);printf("\n");return 0;
}

总结与反思：

1. 还是审题不清。没有注意到负数的问题。
2. 破环成链是解决环上问题的经典方法。

这篇关于283. 多边形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---