建站套餐推荐,怎么优化百度关键词,视频剪辑自学网站,婚庆手机版网站建设一道警钟一样的好题 解析
乍一看#xff1a; “这不就能量项链嘛#xff0c;这也蓝#xff1f;”
然后就愉快的WA掉了… qwq
让我们回归本源#xff0c;在什么时候可以动态规划#xff1f; “局部最优解可以带动全局最优解的时候#xff0c;我们可以使用动态规划算法”… 一道警钟一样的好题 解析
乍一看 “这不就能量项链嘛这也蓝”
然后就愉快的WA掉了… qwq
让我们回归本源在什么时候可以动态规划 “局部最优解可以带动全局最优解的时候我们可以使用动态规划算法” 然而在本题中却不满足这个条件 局部的最大值不一定会导致全局的最优 当另一边为负时局部取最大反而是最差的结果 所以应该维护一个最小值考虑从两方面进行转移
以后写类似的题一定要多想一想不能想当然
代码
#includebits/stdc.h
using namespace std;
const int N120;
const int mod1e97;
double eps1e-10;
#define ll long long
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();};return x*f;
}int n,m;int x[N],op[N];
int mx[N][N],mn[N][N];
//1: add 2:multiply
int q[N],num;
int main(){memset(mx,-0x3f,sizeof(mx));memset(mn,0x3f,sizeof(mn));nread();for(int i1;in;i){char c;scanf( %c%d,c,x[i]);op[i]ct?1:2;}for(int in1;i2*n;i){x[i]x[i-n];op[i]op[i-n];}for(int i1;in*2;i) mn[i][i]mx[i][i]x[i];for(int len2;lenn;len){for(int l1;llen-12*n;l){int rllen-1;for(int il;ir;i){if(op[i1]1){mx[l][r]max(mx[l][r],mx[l][i]mx[i1][r]);mn[l][r]min(mn[l][r],mn[l][i]mn[i1][r]);}else{mx[l][r]max(mx[l][r],max(mx[l][i]*mx[i1][r],mn[l][i]*mn[i1][r]));mn[l][r]min(mn[l][r],min(mx[l][i]*mx[i1][r],mn[l][i]*mn[i1][r]));}}}}int ans(-2e9);for(int i1;in;i){int omx[i][in-1];if(anso){anso;q[num1]i;}else if(anso) q[num]i;}printf(%d\n,ans);for(int i1;inum;i) printf(%d ,q[i]);return 0;
}
/*
2 2 1
1 1
2 1 1
*/
