题意描述
思路
使用
f
[
i
]
[
j
]
f[i][j]
f[i][j]来表示已经选择了
i
i
i段数，并且从前
j
j
j个数选择时的和的最大值。易得转移方程
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
]
[
j
−
1
]
,
f
[
i
−
1
]
[
k
]
)
+
a
[
j
]
，
i
≤
k
≤
j
−
1
f[i][j]=max(f[i][j-1],f[i-1][k])+a[j] ，i≤k≤j-1
f[i][j]=max(f[i][j−1],f[i−1][k])+a[j]，i≤k≤j−1。转移方程的含义为以第
j
j
j个数为新的一组或将
a
[
j
]
a[j]
a[j]分配到前一个组中。由于题目中的
n
n
n和
m
m
m太大，所以这样一定会超内存。观察发现，
f
[
i
−
1
]
[
j
−
1
]
f[i-1][j-1]
f[i−1][j−1]可以使用
p
r
e
[
j
−
1
]
pre[j-1]
pre[j−1]来表示，并且状态方程也可以像背包问题一样优化掉一维，从而得到转移方程
f
[
i
]
=
m
a
x
(
f
[
i
−
1
]
,
p
r
e
[
i
−
1
]
)
+
a
[
i
]
f[i]=max(f[i-1],pre[i-1])+a[i]
f[i]=max(f[i−1],pre[i−1])+a[i]。
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std
;
typedef unsigned long long ull
;
typedef pair
<int,int> PII
;
typedef pair
<char,char> PCC
;
typedef long long ll
;
typedef pair
<ll
,ll
> PLL
;
const int N
=1e6+10;
const int M
=1e6+10;
const int INF
=0x3f3f3f3f;
const int MOD
=1e9+7;
int a
[N
],f
[N
],pre
[N
];
void solve(){
int n
,m
;
while(scanf("%d%d",&m
,&n
)!=EOF){
mst(f
,0);
mst(pre
,0);
for(int i
=1;i
<=n
;i
++) scanf("%d",&a
[i
]);
int res
;
for(int i
=1;i
<=m
;i
++){
res
=-1e9;
for(int j
=i
;j
<=n
;j
++){
f
[j
]=max(f
[j
-1]+a
[j
],pre
[j
-1]+a
[j
]);
pre
[j
-1]=res
;
res
=max(res
,f
[j
]);
}
}
printf("%d\n",res
);
}
}
int main(){
solve();
return 0;
}
