做公司网站哪家 上海,女子拿快递被感染新冠,手机网站开发 手机模拟器,外贸公司网站建设哪家好洛谷 P1063 题意#xff1a;在一串项链中#xff0c;是环状的#xff0c;第 i 颗珠子有两个能量a[i]和a[i1],第i1颗珠子有两个能量a[i1]和a[i2],可以合并两个珠子#xff0c;得到a[i]*a[i1]*a[i2]的能量#xff0c;这两个珠子合并成a[i]和a[i2]的新珠子#xff0c;问通过…洛谷 P1063 题意在一串项链中是环状的第 i 颗珠子有两个能量a[i]和a[i1],第i1颗珠子有两个能量a[i1]和a[i2],可以合并两个珠子得到a[i]*a[i1]*a[i2]的能量这两个珠子合并成a[i]和a[i2]的新珠子问通过合理的操作能得到的最大的能量。 思路区间dp首先环状的变成链状的要把区间翻倍复制枚举左右端点和每个区间的分界点得到结果。注意要先从小到大枚举右端点。 当然也可以开用最外层枚举区间长度得方法。 #include iostream
#include cstdio
#include algorithm
#include cstring
#include string
#include vector
#include map
#include set
#include queue
#include list
#include cstdlib
#include iterator
#include cmath
#include iomanip
#include bitset
#include cctype
using namespace std;
//#pragma comment(linker, /STACK:102400000,102400000) //c
#define lson (l , mid , rt 1)
#define rson (mid 1 , r , rt 1 | 1)
#define debug(x) cerr #x x \n;
#define pb push_back
#define pq priority_queuetypedef long long ll;
typedef unsigned long long ull;typedef pairll ,ll pll;
typedef pairint ,int pii;//priority_queueint q;//这是一个大根堆q
//priority_queueint,vectorint,greaterint q;//这是一个小根堆q
#define fi first
#define se second
//#define endl \n#define OKC ios::sync_with_stdio(false);cin.tie(0)
#define FT(A,B,C) for(int AB;A C;A) //用来压行
#define REP(i , j , k) for(int i j ; i k ; i)
//priority_queueint ,vectorint, greaterint que;const ll mos 0x7FFFFFFF; //2147483647
const ll nmos 0x80000000; //-2147483648
const int inf 0x3f3f3f3f;
const ll inff 0x3f3f3f3f3f3f3f3f; //18
const double PIacos(-1.0);templatetypename T
inline T read(Tx){x0;int f0;char chgetchar();while (ch0||ch9) f|(ch-),chgetchar();while (ch0ch9) xx*10ch-0,chgetchar();return xf?-x:x;
}
// #define _DEBUG; //*//
#ifdef _DEBUG
freopen(input, r, stdin);
// freopen(output.txt, w, stdout);
#endif
/*-----------------------show time----------------------*/const int maxn 109;int n;int a[maxn*2];int dp[maxn*2][maxn*2];
int main(){ OKC;cinn;for(int i1; in; i){cina[i];a[in] a[i];}int ans 0;for(int ri1; ri2*n-1; ri){for(int leri-1; ri-le1 nle1; le--){for(int kle; kri; k){dp[le][ri] max(dp[le][ri] , dp[le][k] dp[k1][ri] a[le]*a[k1]*a[ri1]);ans max(ans, dp[le][ri]);}}}coutansendl;return 0;
} 洛谷 P1063 转载于:https://www.cnblogs.com/ckxkexing/p/9435767.html
