(luogu4342)Polygon(IOI1998) 发表于 2021-02-04 | 分类于 solution , dp 原题链接 思路:一眼看上去是个裸的区间dp, 但是直接套石子合并的话会WA. 由于乘法运算的存在, 可能会有负负得正的情况出现, 所以记录最大值时同时要记录最小值. 然后状态转移方程中同时考虑两者即可. 代码:12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include <iostream>#include <algorithm>#include <climits>using namespace std;const int Mn(205);long long an[Mn]; //数字bool ao[Mn]; //符号, ao[i]表示i与i+1之间的符号long long dp[Mn][Mn],dn[Mn][Mn]; //最大值与最小值(区间起点,区间长度)int main() { ios::sync_with_stdio(false); int n; cin >> n; char op; cin >> op; //先输入第一个运算符更方便处理 ao[n] = (op=='x'); for(int i(1);i<n;++i) { cin >> an[i] >> op; an[i+n] = an[i]; //"化环为链" ao[i+n] = ao[i] = (op=='x'); //同上 } cin >> an[n]; for(int i(1);i<2*n;++i) { dp[i][1] = dn[i][1] = an[i]; //初始化 } for(int l(2);l<=n;++l) { //枚举区间长度 for(int i(1);i+l-1<2*n;++i) { //枚举区间起点 /*----状态转移----*/ if(ao[i]) { dp[i][l] = max(dp[i+1][l-1] * an[i], dn[i+1][l-1] * an[i]); dn[i][l] = min(dp[i+1][l-1] * an[i], dn[i+1][l-1] * an[i]); } else { dp[i][l] = dp[i+1][l-1] + an[i]; dn[i][l] = dn[i+1][l-1] + an[i]; } for(int k(i+1);k<i+l-1;++k) { if(ao[k]) { /*----乘法时由于"负负得正"需要考虑四种情况----*/ dp[i][l] = max(dp[i][l],dp[i][k-i+1] * dp[k+1][l-k+i-1]); dp[i][l] = max(dp[i][l],dp[i][k-i+1] * dn[k+1][l-k+i-1]); dp[i][l] = max(dp[i][l],dn[i][k-i+1] * dn[k+1][l-k+i-1]); dp[i][l] = max(dp[i][l],dn[i][k-i+1] * dp[k+1][l-k+i-1]); dn[i][l] = min(dn[i][l],dp[i][k-i+1] * dp[k+1][l-k+i-1]); dn[i][l] = min(dn[i][l],dp[i][k-i+1] * dn[k+1][l-k+i-1]); dn[i][l] = min(dn[i][l],dn[i][k-i+1] * dn[k+1][l-k+i-1]); dn[i][l] = min(dn[i][l],dn[i][k-i+1] * dp[k+1][l-k+i-1]); } else { /*----加法则不需要----*/ dp[i][l] = max(dp[i][l],dp[i][k-i+1] + dp[k+1][l-k+i-1]); dn[i][l] = min(dn[i][l],dn[i][k-i+1] + dn[k+1][l-k+i-1]); } } } } /*----输出答案----*/ long long ans(LONG_LONG_MIN); for(int i(1);i<=n;++i) { ans = max(ans,dp[i][n]); } cout << ans << endl; for(int i(1);i<=n;++i) { if(dp[i][n]==ans) { cout << i << " "; } } return 0;}