poj 1157(SGU 104) 동적 기획(꽃병 꽃꽂이)
사고방식: 동태적 기획.pp[i][j]는 전 i종의 꽃이 전 j개의 꽃병에 삽입된 최대 미관을 나타낸다.i꽃에 대한 분류: 1. i꽃이 j번째 꽃병에 꽂히면 dp[i][j]=dp[i-1][j-1]+s[i][j];2. 제j번째 꽃병이 비어 있으면 dp[i][j]=dp[i][j-1];
요약하면 상태 방정식은 dp[i][j]=max(dp[i-1][j-1]+s[i][j], dp[i][j-1])이다.
주의: 미관 정도의 범위가 [-50,50]이기 때문에 처리해야 한다. 미관 정도에 50을 더하고 마지막에 n*50을 빼야 한다.
SGU 104는 Poj라는 제목의 설명과 완전히 같지만 다른 출력 방안이 필요합니다.하나의 수조로 돌아가는 경로를 기록하고, 돌아가는 출력을 하면 된다.
#include <stdio.h>
#include <string.h>
#define N 102
#define MIN -0x3fffffff
#define max(a,b) a>b?a:b
int n,m;
int dp[N][N],s[N][N];
int main(){
freopen("a.txt","r",stdin);
while(scanf("%d %d",&n,&m)!=EOF){
int i,j;
memset(dp,0,sizeof(dp));
for(i = 1;i<=n;i++)
for(j = 1;j<=m;j++){
scanf("%d",&s[i][j]);
}
for(i = 1;i<=n;i++)
for(j = 1;j<=m;j++)
dp[i][j] = max(dp[i-1][j-1]+s[i][j]+50,dp[i][j-1]);
printf("%d
",dp[n][m]-n*50);
}
return 0;
}SGU104 추가 출력 시나리오의 코드:
#include <stdio.h>
#include <string.h>
#define N 105
int v[N][N],dp[N][N],path[N][N];
int n,m;
void print(int x,int y){
int i;
if(!x)
return ;
for(i = y;i>=1;i--){
if(path[x][i] == 2){// x i i
print(x-1,i-1);
if(x != n)
printf("%d ",i);
else
printf("%d
",i);
return ;
}
}
}
int main(){
int i,j;
freopen("a.txt","r",stdin);
memset(dp,0,sizeof(dp));
scanf("%d %d",&n,&m);
for(i = 1;i<=n;i++)
for(j = 1;j<=m;j++){
scanf("%d",&v[i][j]);
v[i][j] += 50;
}
for(i = 1;i<=n;i++){
for(j = 1;j<=m;j++)
if(dp[i-1][j-1]+v[i][j] >= dp[i][j-1]){
dp[i][j] = dp[i-1][j-1] + v[i][j];
path[i][j] = 2;
}else{
dp[i][j] = dp[i][j-1];
path[i][j] = 1;
}
}
printf("%d
",dp[n][m]-n*50);
print(n,m);
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
