dp优化我总是不太熟练。这一次首先我写了O(n4)->O(n3)->O(n2)。一步步的优化过来。yyl好像用的是单调队列优化dp我看不懂他的代码。。。
O(n4)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
ll read(){
ll x=0,f=1;char c=getchar();
while(!isdigit(c)) {
if(c=='-') f=-1;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}
const int nmax=5e3+5;
const ll inf=1e18;
ll dp[nmax],g[nmax],sm[nmax];
int main(){
int n=read(),m=read();ll u,v,d;
rep(i,1,n) sm[i]=sm[i-1]+read();
rep(i,1,m) {
rep(j,i,n) {
rep(k,0,j-1) {
u=inf;
rep(t,k+1,j) u=min(u,sm[t]);
dp[j]=max(dp[j],g[k]+sm[j]-u);
}
}
rep(j,1,n) g[j]=dp[j];
}
ll ans=0;
rep(i,m,n) ans=max(ans,dp[i]);
printf("%lld\n",ans);
return 0;
}
O(n3)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
ll read(){
ll x=0,f=1;char c=getchar();
while(!isdigit(c)) {
if(c=='-') f=-1;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}
const int nmax=5e3+5;
const ll inf=1e18;
ll dp[nmax],g[nmax],sm[nmax];
int main(){
int n=read(),m=read();ll u,v,d,tm=0,cnt=0;
rep(i,1,n) {
sm[i]=sm[i-1]+(u=read());
if(u) ++cnt,tm+=u;
}
if(m>=cnt) {
printf("%lld\n",tm);return 0;
}
rep(i,1,m) {
rep(j,i,n) {
dp[j]=dp[j-1];
rep(k,0,j-1) dp[j]=max(dp[j],g[k]+sm[j]-sm[k]);
}
rep(j,1,n) g[j]=dp[j];
}
printf("%lld\n",dp[n]);
return 0;
}
O(n2)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
ll read(){
ll x=0,f=1;char c=getchar();
while(!isdigit(c)) {
if(c=='-') f=-1;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}
const int nmax=5e3+5;
const ll inf=1e18;
ll dp[nmax],sm[nmax],f[nmax];
int main(){
int n=read(),m=read();ll u,v,d,tm=0,cnt=0;
rep(i,1,n) {
sm[i]=sm[i-1]+(u=read());
if(u) ++cnt,tm+=u;
}
if(m>=cnt) {
printf("%lld\n",tm);return 0;
}
f[0]=-inf;rep(j,1,n) f[j]=max(f[j-1],dp[j-1]-sm[j-1]);
rep(i,1,m) {
rep(j,i,n) dp[j]=max(dp[j-1],f[j]+sm[j]);
f[0]=-inf;rep(j,1,n) f[j]=max(f[j-1],dp[j-1]-sm[j-1]);
}
printf("%lld\n",dp[n]);
return 0;
}
基准时间限制：2 秒 空间限制：131072 KB 分值: 80 难度：5级算法题
收藏
关注N个整数组成的序列a[1],a[2],a[3],…,a[n]，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。如果M >= N个数中正数的个数，那么输出所有正数的和。
例如：-2 11 -4 13 -5 6 -2，分为2段，11 -4 13一段，6一段，和为26。
Input
第1行：2个数N和M，中间用空格分隔。N为整数的个数，M为划分为多少段。（2 <= N , M <= 5000)
第2 - N+1行：N个整数 (-10^9 <= a[i] <= 10^9)
Output
输出这个最大和
Input示例
7 2
-2
11
-4
13
-5
6
-2
Output示例
26