做招商网站的前景怎么样,吴江设计网站公司,门户网站与网站的区别,做网站前台需要什么技能Problem - 1796D - Codeforces 思路#xff1a;想了个假dp做法推了半天#xff0c;果然是dp。考虑用dp[i][j]表示以i结尾的#xff0c;并且选择j个#xff0b;x的最长连续子序列#xff0c;那么如果我不选择第i位#xff0c;那么会有f[i][j]max(w[i]-x,f[i-1][j]w[i]-x)想了个假dp做法推了半天果然是dp。考虑用dp[i][j]表示以i结尾的并且选择j个x的最长连续子序列那么如果我不选择第i位那么会有f[i][j]max(w[i]-x,f[i-1][j]w[i]-x)同时ij也要满足因为如果ij那么所有的我必须都要选择如果第i位我选择那么会有
f[i][j]max(w[i]x,f[i-1][j-1]w[i]x)同时要满足j-10另外我们还要保证我们总共要选择k个在前i个中我们选择了j个那么要满足在n-i中至少选择k-j个即要满足n-ik-j所以jk-ni所以我们只要算所有的f[i][j]同时取一个max即可因为我们保证了我们枚举到的i,j都满足总共要选择k个的条件
// Problem: D. Maximum Subarray
// Contest: Codeforces - Educational Codeforces Round 144 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/1796/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms#includeiostream
#includecstring
#includestring
#includesstream
#includebitset
#includedeque
#includecmath
#includecstdio
#includealgorithm
#includequeue
#includemap
#includestack
#includevector
#includeset
#includecstdlib
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pairint,int PII;
typedef pairint,pairint,int PIII;
const double eps1e-7;
const int N5e57 ,M5e57, INF0x3f3f3f3f,mod1e97,mod1998244353;
const long long int llINF0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x0,f1;char cgetchar();while(c0||c9) {if(c-) f-1;cgetchar();}
while(c0c9) {x(ll)x*10c-0;cgetchar();} return x*f;}
inline void write(ll x) {if(x 0) {putchar(-); x -x;}if(x 10) write(x / 10);putchar(x % 10 0);}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen(in_put.txt,r,stdin);freopen(my_out_put.txt,w,stdout);}
bool cmp0(int a,int b) {return ab;}
templatetypename T T gcd(T a,T b) {return b0?a:gcd(b,a%b);}
templatetypename T T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf(\n----------------------------------\n);}int T,hackT;
int n,m,k;
int w[N];
ll f[N][21];void solve() {nread(),kread();int xread();for(int i1;in;i) w[i]read();for(int i1;in;i) {for(int j0;jk;j) {f[i][j]-llINF;}}ll res0;for(int i1;in;i) {for(int jmax(0,ki-n);jmin(i,k);j) {if(ji) f[i][j]max((ll)w[i]-x,f[i-1][j]w[i]-x);if(j0) f[i][j]max(f[i][j],max((ll)w[i]x,f[i-1][j-1]w[i]x));f[i][j]max(f[i][j],0ll);resmax(res,f[i][j]);}}printf(%lld\n,res);
} int main() {// init();// stin();scanf(%d,T);// T1; while(T--) hackT,solve();return 0;
} 参考博客https://www.cnblogs.com/onlyblues/p/17177714.html
这个博客讲的挺详细的
