RQNOJ 꽃집 쇼윈도 배치
2092 단어 OJ
사고방식: 동적 기획 분석: 1 제목은 가장 큰 미학적 값을 찾아야 하고 표지 번호가 큰 것은 표지 번호가 작은 오른쪽에 있어야 한다. 그러면 꽃 i가 i행의 j열에 있으면 i+1송이가 j+1 뒤의 2가 뚜렷한 단계에 나와야 한다는 것을 알 수 있다. 우리는 dp[i][j]로 첫 번째 꽃을 j열에 놓으면 얻을 수 있는 최대 미학적 값을 나타낸다. 그러면 dp[i][j]=max(dp[i-1][j])+num[j];여기에 꽃이 많을 때마다 놓을 수 있는 구간을 주의해야 한다. i번이 많으면 놓을 수 있는 구간이 i행이다. [i~V-F+n] 3문제는 꽃이 많지 않은 위치를 출력해야 한다. 그러면 상태가 이동할 때 위치를 기록하면 코드가 된다.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 1<<30;
const int MAXN = 110;
int n , m;
int num[MAXN][MAXN] , dp[MAXN][MAXN];
int path[MAXN][MAXN] , output[MAXN];
void solve(){
for(int i = 1 ; i <= m-n+1 ; i++)
dp[1][i] = num[1][i];
memset(path , -1 , sizeof(path));
for(int i = 2 ; i <= n ; i++){
for(int j = i ; j <= m-n+i ; j++){
dp[i][j] = num[i][j];
int Max = -INF;
int pos;
for(int k = i-1 ; k < j ; k++){
if(dp[i-1][k] > Max){
Max = max(Max , dp[i-1][k]);
pos = k;
}
}
dp[i][j] += Max;
path[i][j] = pos;
}
}
int ans = -INF;
int pos , x , y;
for(int i = n ; i <= m ; i++){
if(ans < dp[n][i]){
ans = max(ans , dp[n][i]);
y = i;
}
}
printf("%d
" , ans);
pos = n-1;
x = n;
output[pos--] = y;
while(path[x][y] != -1){
output[pos--] = path[x][y];
y = path[x--][y];
}
printf("%d" , output[0]);
for(int i = 1 ; i < n ; i++)
printf(" %d" , output[i]);
printf("
");
}
int main(){
while(scanf("%d%d" , &n , &m) != EOF){
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= m ; j++)
scanf("%d" , &num[i][j]);
solve();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdoj1006--Tick and TickA hand is happy if it is at least D degrees from any of the rest. Input The input is terminated with a D of -1. For each...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.