#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 25;
struct node {//dp节点
int cnt = 0;//前面已选上的行的个数
int in[maxn];//前面已选上的行标
ll s = 0;//总分
};
int map[maxn][maxn];
int mix[maxn][maxn * 2];
int sum[maxn * 2];
node dp[maxn * 2][maxn * 2];//dp[i][j]前i个选j个
int main(void)
{
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
if (k > m + n)k = m + n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &map[i][j]), mix[i][n + j] = map[i][j];//
for (int i = 1; i <= n; i++)
{
ll t = 0;
for (int j = 1; j <= m; j++)
t += map[i][j];
sum[i] = t;
}
for (int j = 1; j <= m; j++)
{
ll t = 0;
for (int i = 1; i <= n; i++)
t += map[i][j];
sum[j + n] = t;//把每行sum和每列sum排成一维,前n个为行,后m个为列
}
for (int i = 1; i <= n + m; i++)
for (int j = 1; j <= k; j++)
{
ll t = sum[i];
for (int z = 0; i > n&& z < dp[i - 1][j - 1].cnt; z++)
t -= mix[dp[i - 1][j - 1].in[z]][i];
if (dp[i - 1][j - 1].s + t > dp[i - 1][j].s) {
dp[i][j] = dp[i - 1][j - 1];
dp[i][j].s += t;
if (i <= n)
dp[i][j].in[dp[i][j].cnt++] = i;
}
else
dp[i][j] = dp[i - 1][j];
}
ll ans = 0;
for (int i = k; i <= n + m; i++)
ans = max(ans, dp[i][k].s);
printf("%lld", ans);
return 0;
}
82.5%
全部评论
(0) 回帖