题解 - Vijos

1

孙鹤鸣 (sunheming) LV 10 @ 2020-11-23 16:24:13

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=110;
const int M=11;
int n,m,K,s1[N],s2[N],dp[N][M],f[N][N][M];
int main(){
    scanf("%d%d%d",&n,&m,&K);
    if(m==1){
        for(int i=1,x;i<=n;i++) scanf("%d",&x),s1[i]=s1[i-1]+x;
        for(int k=1;k<=K;k++){
            for(int i=1;i<=n;i++){
                dp[i][k]=dp[i-1][k];
                for(int j=0;j<i;j++) dp[i][k]=max(dp[i][k],dp[j][k-1]+s1[i]-s1[j]);
            }
        }
        printf("%d\n",dp[n][K]);
    }
    else{
        for(int i=1,x,y;i<=n;i++) scanf("%d%d",&x,&y),s1[i]=s1[i-1]+x,s2[i]=s2[i-1]+y;
        for(int k=1;k<=K;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);
                    for(int l=0;l<i;l++) f[i][j][k]=max(f[i][j][k],f[l][j][k-1]+s1[i]-s1[l]);
                    for(int l=0;l<j;l++) f[i][j][k]=max(f[i][j][k],f[i][l][k-1]+s2[j]-s2[l]);
                    if(i==j)  for(int l=0;l<i;l++) f[i][j][k]=max(f[i][j][k],f[l][l][k-1]+s1[i]-s1[l]+s2[j]-s2[l]);
                }
            }
        }
        printf("%d\n",f[n][n][K]);
    }
    return 0;
}

0

MBAPPE (MBAPPE) LV 8 @ 2019-10-02 19:36:24

QWQ

0

z20c12h LV 9 @ 2017-07-25 20:40:31

从思考到抄题解。

#include<iostream>
#include<cstring>
#define INF (0x3f3f3f3f)
#define MAX(a,b) ((a)=((a)>(b)?(a):(b)))
using namespace std;
int n,m,k;
int da[110][5],sum[110][5],dp[110][110][20];
int main () {
    
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) 
      for(int j=1;j<=m;j++) {
          cin>>da[i][j];
          sum[i][j]=sum[i-1][j]+da[i][j];   
          if (m==1) sum[i][2]=-INF; 
      }
    int ans=-INF;
    for(int i=1;i<=n;i++)  
      for(int j=1;j<=n;j++)
        for(int o=1;o<=k;o++) {
            MAX(dp[i][j][o],dp[i-1][j][o]);
            MAX(dp[i][j][o],dp[i][j-1][o]);
            MAX(dp[i][j][o],dp[i-1][j-1][o]);
            for(int p=0;p<i;p++) MAX(dp[i][j][o],dp[p][j][o-1]+sum[i][1]-sum[p][1]);
            for(int p=0;p<j;p++) MAX(dp[i][j][o],dp[i][p][o-1]+sum[j][2]-sum[p][2]);    
            if (i==j) for(int p=0;p<i;p++) MAX(dp[i][j][o],dp[p][p][o-1]+sum[i][1]-sum[p][1]+sum[j][2]-sum[p][2]);   
            ans=max(ans,dp[i][j][o]);
        }
    cout<<ans<<endl;    
    return 0;
    
}

-1

Lyhgod LV 7 @ 2016-03-10 10:31:53

VIJOS逗我，NOI OJ AC在这就一个点？

#include<cstdio>
#include<cstring>
int a[110][110],b[110][110];
int maxsum(int x,int y){return x>y?x:y;}
int main()
{
int n,sum,ans;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
if(i==1)b[i][j]=a[i][j];
else b[i][j]=b[i-1][j]+a[i][j];
}
}
ans=-1;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
sum=b[j][1]-b[i-1][1];
int s=0;
for(int k=1;k<=n;k++)
{
s+=b[j][k]-b[i-1][k];
if(s>sum)sum=s;
if(s<0)s=0;
}
ans=maxsum(sum,ans);
}
}
printf("%d\n",ans);
return 0;
}

-1

JSZX11556 LV 9 @ 2016-02-12 18:31:59

http://www.cnblogs.com/JSZX11556/p/4732568.html dp

-1

acmicpc LV 9 @ 2015-12-14 18:29:04

DP
http://www.cnblogs.com/jimzeng/p/bzoj1084.html

-1

ws_lhf LV 9 @ 2013-10-30 09:05:04

测试数据 #0: Accepted, time = 15 ms, mem = 2444 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 2448 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2448 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2444 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 2444 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 2444 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 2448 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 2448 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 2444 KiB, score = 10
测试数据 #9: WrongAnswer, time = 15 ms, mem = 2448 KiB, score = 0
WrongAnswer, time = 90 ms, mem = 2448 KiB, score = 90
代码
var
a:array[0..200,0..200]of longint;
d,gg,g:array[1..3,0..200,0..200]of longint;
f:array[0..101,0..101]of longint;
n,m,k,l,i,j,p:longint;
function max(x,y:longint):longint;
begin
if x>y then max:=x else max:=y;
end;
begin

readln(n,m,k);
for i:=1 to n do
for j:=1 to m do
read(a[j,i]);
for i:=1 to n do
a[3,i]:=a[1,i]+a[2,i];
for i:=1 to 3 do{d数组可无视}
for j:=1 to n do
for l:=j to n do
d[i,j,l]:=d[i,j,l-1]+a[i,l];

fillchar(g,sizeof(g),128);
for i:=1 to 3 do
for j:=1 to n do
for l:=j to n do
begin
for p:=j to l do
gg[i,j,p]:=max(gg[i,j,p-1]+a[i,p],a[i,p]);
for p:=j to l do
g[i,j,l]:=max(g[i,j,l],gg[i,j,p]);
end;

fillchar(f,sizeof(f),128);
f[0,0]:=0;
for i:=1 to n do
for j:=1 to k do
for l:=0 to i-1 do
begin
for p:=1 to 3 do
if (f[i,j]<f[l,j-1]+g[p,l+1,i]) then
f[i,j]:=f[l,j-1]+g[p,l+1,i];
if (j>=2)and(g[1,l+1,i]+g[2,l+1,i]+f[l,j-2]>f[i,j]) then
f[i,j]:=g[1,l+1,i]+g[2,l+1,i]+f[l,j-2];
end;
writeln(f[n,k]);
end.
最后一个点是咋回事啊...

-1

chengrui LV 10 @ 2009-11-03 16:24:15

编译通过...

├ 测试数据 01：答案正确... 56ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：81ms

1,2分开写，好暴力的俄......

碰到好的评测机，就81MS过 - -！

瀑布汗

-1

181818181818 LV 10 @ 2009-10-18 11:54:13

m好小哦，如果m也100就麻烦了

-1

yzl609271536 LV 10 @ 2009-10-10 08:32:34

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 150ms

├ 测试数据 10：答案正确... 306ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：456ms

好丑的时间

-1

陈亮宇 LV 10 @ 2009-10-09 16:17:40

两种情况合起来更方便吧

-1

一Six个性 LV 8 @ 2009-10-08 17:23:51

感谢rlf大牛这道神题终于过了。。这种题不要记忆化搜索

-1

FenXy LV 10 @ 2009-09-23 19:01:08

http://blog.sina.com.cn/s/blog_5774b8650100f98g.html

-1

qihongjie LV 9 @ 2009-09-03 09:15:33

那位大牛指点一下，不会啊？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

-1

dzs999 LV 8 @ 2009-09-02 13:27:51

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 509ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：509ms

第一个点有什么特殊情况吗....

-1

yby.barty LV 9 @ 2009-07-20 10:07:49

纯水题

#include

using namespace std;

int main()

{

int dp[101][101][11],num[101][3],n,m,k,sum[3][101][101];

memset(dp,0,sizeof(dp));

memset(num,0,sizeof(num));

cin >> n >> m >> k;

for (int i=1;i num[i][j];

for (int s=1;s

-1

huyuanming11 LV 10 @ 2009-06-19 00:37:45

此题一题抵2题......

-1

voyagec2 LV 10 @ 2009-03-18 16:17:19

第100个AC，顺便提高通过率一个百分点，DP

编译通过...

├ 测试数据 01：答案正确... 1000ms

├ 测试数据 02：答案正确... 1000ms

├ 测试数据 03：答案正确... 1000ms

├ 测试数据 04：答案正确... 1000ms

├ 测试数据 05：答案正确... 1000ms

├ 测试数据 06：答案正确... 1000ms

├ 测试数据 07：答案正确... 1000ms

├ 测试数据 08：答案正确... 1000ms

├ 测试数据 09：答案正确... 1000ms

├ 测试数据 10：答案正确... 1000ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：10000ms

要说楼下的楼下，我这才叫危险

-1

wu3412790 LV 10 @ 2008-11-11 17:16:58

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

-1

LV.唱响 LV 8 @ 2008-11-06 15:31:04

编译通过...

├ 测试数据 01：答案正确... 999ms

├ 测试数据 02：答案正确... 999ms

├ 测试数据 03：答案正确... 999ms

├ 测试数据 04：答案正确... 999ms

├ 测试数据 05：答案正确... 999ms

├ 测试数据 06：答案正确... 999ms

├ 测试数据 07：答案正确... 999ms

├ 测试数据 08：答案正确... 999ms

├ 测试数据 09：答案正确... 999ms

├ 测试数据 10：答案正确... 999ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9990ms

很危险的时间。

Randle @ 2017-07-26 11:29:48

我怎么觉得是卡过去的？

题解

39 条题解

最大子矩阵

信息

状态

开发

支持

题解

39 条题解

最大子矩阵

信息

状态

开发

支持

还没有账户？

登录