[BZOJ 1084] [SCOI 2005] 최대 서브 매트릭스 바 보 큐 게이지
1725 단어 동적 계획최대 서브 매트릭스SCOI2005BZOJ1084
문제 풀이:
이 데이터 범위, 마구 잡 이 로 하 세 요, 소년.
나의 난 장 판:
m = = 1 시 에 한 번 하고 m = 2 시 에 한 번 한다.
적은 상황 만 토론 하지 마 세 요. m = 2 시 시간 복잡 도 n ^ 3.
코드:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 105
using namespace std;
int map[N][3],s[N][3],sum[N];
int f[N][N][12],g[N][12];
int n,m,p;
int main()
{
// freopen("test.in","r",stdin);
int i,j,k,t;
scanf("%d%d%d",&n,&m,&p);
for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&map[i][j]);
if(m==1)
{
for(i=1;i<=n;i++)sum[i]=sum[i-1]+map[i][1];
for(k=1;k<=p;k++)
{
for(i=1;i<=n;i++)
{
g[i][k]=max(g[i-1][k],g[i][k-1]);
for(j=1;j<i;j++)
g[i][k]=max(g[i][k],g[j][k-1]+sum[i]-sum[j]);
}
}
printf("%d
",g[n][p]);
}
else {
for(i=1;i<=n;i++)
{
s[i][1]=s[i-1][1]+map[i][1];
s[i][2]=s[i-1][2]+map[i][2];
s[i][0]=s[i][1]+s[i][2];
}
for(k=0;k<=p;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{
if(i)f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);
if(j)f[i][j][k]=max(f[i][j][k],f[i][j-1][k]);
if(k)f[i][j][k]=max(f[i][j][k],f[i][j][k-1]);
if(i&&j)f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]);
for(t=i+1;t<=n;t++)f[t][j][k+1]=max(f[t][j][k+1],f[i][j][k]+s[t][1]-s[i][1]);
for(t=j+1;t<=n;t++)f[i][t][k+1]=max(f[i][t][k+1],f[i][j][k]+s[t][2]-s[j][2]);
int temp=max(i,j);
for(t=temp+1;t<=n;t++)f[t][t][k+1]=max(f[t][t][k+1],f[i][j][k]+s[t][0]-s[temp][0]);
}
printf("%d
",f[n][n][p]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JZOJ.3432 [GDOI 2014 시뮬레이션] 서버 문제 해결 보고서이 서버의 번호는 1, 2,..., n이다.우선, 우리는 일부 서버를 선택하여 파일을 그것들에 직접 복사할 수 있다.서버 i에 파일을 복사하려면 ci가 필요합니다.직접 복제를 통해 파일을 얻지 못한 서버에 대해 i+...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.