1.HDU1024 Max Sum Plus Plus 最大M子段和
\(dp[i][j]\)表示以第j个数结尾且被分为i段的最大子段和，答案即是\(dp[m][n]\)。
与单集合（\(m=1\)）的最大字段和不同的点在于，本题需要组成\(m\)个不相交的最大子段，因而对状态转移方程进行修改：
-
第一种情况：第\(j\)个数纳入前\(j-1\)个数的最右最大子段中，即\(dp[i][j]=dp[i][j-1]+a[j]\)
-
第二种情况：第\(j\)个数不被纳入最右侧的最大子段，作为第i个子段存在，即\(dp[i][j]=dp[i-1][k]+a[j],k＜j\)。
综上：
\[dp[i][j]=max(dp[i][j-1]+a[j],dp[i-1][k]+a[j]) \]注意到范围\(n\leq 1e6,m\)虽然很小不会卡成\(O(n^2)\)，但依然会\(MLE\)，故考虑滚动数组优化：
\[dp[j]=max(dp[j-1]+a[j],last[j-1]+a[j]) \]其中\(last[j]\)表示前j个\(dp[j]\)的最大值，通过滚动数组维护并更新。
复杂度\(O(mn-m^2/2)\)
#include<cstdio>
#include<iostream>
#include<cstring>
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int n, m, a[maxn];
int f[maxn], last[maxn];
int tmp = -inf;
void dp() {
for (int i = 1; i <= m; i++) {
tmp = -inf;
for (int j = i; j <= n; j++) {//j<i是无法分出i组子段的
f[j] = std::max(f[j - 1] + a[j], last[j - 1] + a[j]);
last[j - 1] = tmp;
tmp = std::max(tmp, f[j]);
}
}
}
int main() {
while (scanf("%d%d", &m, &n) == 2) {
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
memset(f, 0, sizeof(f));
memset(last, 0, sizeof(last));
dp();
printf("%d\n", tmp);
}
}
2.Ignatius and the Princess IV 计数？
\(map\)存一下出现次数就行，用不着\(dp\)
#include<iostream>
#include<cstdio>
#include<map>
std::map<int, int> m;
int n, x, ans;
int main() {
while (scanf("%d", &n) == 1) {
m.clear();
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
m[x]++;
if (m[x] >= (n + 1) / 2) {
ans = x;
}
}
printf("%d\n", ans);
}
return 0;
}