本文主要是介绍POJ 1179 Polygon，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：给一个多边形，每个顶点有一个值，每个边编号从1到N，边的属性是加或者乘。首先先拆掉一条边，剩下的如下做：选定一条边以及这条边的两个端点（两个数）用新顶点替换（新顶点即：按照这条边的属性（加或乘）算出这两个数的乘积或者和）。到最后剩一个点，也就是一个值。求这些值的最大值输出，并输出此时最先拆掉的是哪条边。
Input:
4
t -7 t 4 x 2 x 5
Output:
33
1 2
区间DP问题
注意最大值可以由两个最小值相乘得到
注意下标和求min_v和max_v时的逻辑简化
#include <iostream>
#include <vector>
using namespace std;#define SIZE 70
#define MAX_V 0
#define MIN_V 1
#define INF 1 << 15int dp[SIZE][SIZE][2];
char symbols[SIZE];
int node_values[SIZE];
int node_num;
vector< int > v;int cal( int head, int tail, char symbol ){if( symbol == 't' )return head + tail;elsereturn head * tail;
}int main(){cin >> node_num;for( int i = 0; i < node_num; ++i ){cin >> symbols[i] >> node_values[i];}for( int i = 0; i < node_num; ++i )for( int j = 0; j < node_num; ++j )if( i == j )dp[i][i][MAX_V] = dp[i][i][MIN_V] = node_values[i];for( int len = 1; len <= node_num - 1; ++len ){for( int from = 0; from < node_num; ++from ){int to = ( from + len ) % node_num;int min_v = INF;int max_v = -INF;for( int count_ = 0; count_ < len; ++count_ ){int cut = ( from + count_ ) % node_num;int cut1 = ( from + count_ + 1 ) % node_num;int temp = 0;temp = cal( dp[from][cut][MAX_V], dp[cut1][to][MAX_V], symbols[cut1] );max_v = max( temp, max_v );temp = cal( dp[from][cut][MIN_V], dp[cut1][to][MIN_V], symbols[cut1] );max_v = max( temp, max_v );temp = cal( dp[from][cut][MIN_V], dp[cut1][to][MAX_V], symbols[cut1] );min_v = min( temp, min_v );temp = cal( dp[from][cut][MAX_V], dp[cut1][to][MIN_V], symbols[cut1] );min_v = min( temp, min_v );}dp[from][to][MAX_V] = max_v;dp[from][to][MIN_V] = min_v;}}int temp = -INF;for( int from = 0; from < node_num; ++from ){int to = ( from + node_num - 1 ) % node_num;if( dp[from][to][MAX_V] > temp ){temp = dp[from][to][MAX_V];v.clear();v.push_back( from );}else if( dp[from][to][MAX_V] == temp )v.push_back( from );}cout << temp <<endl;for( int i = 0; i < v.size(); ++i )cout << v[i] + 1 << " ";cout << endl;return 0;
}
这篇关于POJ 1179 Polygon的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
