이 dp는 좀 이상하다
2180 단어 Dp
제목:
뚱뚱한 ZSer 선배는 요즘 다이어트를 해서 간식을 못 먹는데 간식을 못 먹는 게 너무 고통스러워요.마침 초등학교 여동생이 그를 찾아와 놀았는데, 그는 생각을 해 보니 좋은 생각이 하나 생겼다. 그는 초등학교 여동생과 함께 간식을 먹을 수 있는 게임을 하려고 한다.게임 규칙은 이렇습니다. 모든 사람은 M*N의 행렬을 가지고 그 안에 칸마다 약간의 행렬이 놓여 있습니다.현재 ZSer 선배는 가능한 한 많은 간식을 먹고 싶지만, 모든 사람은 다음과 같은 게임 규칙을 따라야 한다. (x, y)에서 간식을 먹으면 x-1줄, x+1줄, (x, y-1), (x, y+1)에서 간식을 먹을 수 없다.
문제는 뚱뚱한 선배가 간식을 얼마나 많이 먹을 수 있느냐는 것이다.초등학교 여동생도 맨날 놀러 오는 건 아니니까.
테스트 데이터의 여러 그룹이 있으며 각 그룹의 테스트 데이터에 대해 다음을 수행합니다.
M(행) 및 N(열)을 입력하고 다음 M행은 N개의 정수로 구성되어 간식의 수를 나타냅니다.칸당 간식 수는 1000을 넘지 않으며 1<=M*N<=200000.
M(행) 및 N(열)을 입력하고 다음 M행은 N개의 정수로 구성되어 간식의 수를 나타냅니다.칸당 간식 수는 1000을 넘지 않으며 1<=M*N<=200000.
Output
각 그룹의 테스트 데이터에 대해 다음을 수행합니다.
먹을 수 있는 최대 간식 수를 출력합니다.
Sample Input Copy 4 6
11 0 7 5 13 9
78 4 81 6 22 4
1 40 9 34 16 10
11 22 0 33 39 6
7 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
Sample Output Copy 242
100
제목:
독선적으로 뛰기 시작하면 일렬에 한 번씩 덧붙인다. 결말은 당연히 와와와와와와와와다. 왜냐하면 그의 앞줄만 아니면 그가 가장 큰 것을 먹기 때문이다.그래서 줄언니가 최대치를 한 줄의 마지막 줄에 붙이면 된다고 했어요. 그래서 i-1의 값이나 i-2를 직접 뽑았어요. 그리고 열수도 똑같아요. 마지막으로 우리가 얻은 답은 열수 그룹의 마지막 답이에요.#include
#include
#include
using namespace std ;
long long ss[200040],dp2[200040];
long long dp[200040],maxx;
int main()
{
int m,n;
while(~scanf("%d%d",&m,&n))
{
memset(dp,0,sizeof(dp));
memset(dp2,0,sizeof(dp2));
maxx=0;
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
{
scanf("%d",&ss[j]);
if(j>=2)
dp[j] = max(dp[j-1],dp[j-2]+ss[j]);
else
dp[j]=ss[j];
}
if(i>=2)
dp2[i] = max(dp2[i-1],dp2[i-2]+dp[n]);
else
dp2[i]=dp[n];
}
printf("%d
",dp2[m]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[문제풀이] 루구 5662: 기념품
원제 전송문
열거 현재 며칠째
d p i dp_i dpi는 오늘 원금이 i i i인 경우 오늘 사들이고 내일 팔면 가장 많은 이윤을 얻을 수 있다
즉, 제목의 뜻을 바꾸어 pi+1, j-3-pi, jp 를{i+1,j...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
4 6
11 0 7 5 13 9
78 4 81 6 22 4
1 40 9 34 16 10
11 22 0 33 39 6
7 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9242
100독선적으로 뛰기 시작하면 일렬에 한 번씩 덧붙인다. 결말은 당연히 와와와와와와와와다. 왜냐하면 그의 앞줄만 아니면 그가 가장 큰 것을 먹기 때문이다.그래서 줄언니가 최대치를 한 줄의 마지막 줄에 붙이면 된다고 했어요. 그래서 i-1의 값이나 i-2를 직접 뽑았어요. 그리고 열수도 똑같아요. 마지막으로 우리가 얻은 답은 열수 그룹의 마지막 답이에요.
#include
#include
#include
using namespace std ;
long long ss[200040],dp2[200040];
long long dp[200040],maxx;
int main()
{
int m,n;
while(~scanf("%d%d",&m,&n))
{
memset(dp,0,sizeof(dp));
memset(dp2,0,sizeof(dp2));
maxx=0;
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
{
scanf("%d",&ss[j]);
if(j>=2)
dp[j] = max(dp[j-1],dp[j-2]+ss[j]);
else
dp[j]=ss[j];
}
if(i>=2)
dp2[i] = max(dp2[i-1],dp2[i-2]+dp[n]);
else
dp2[i]=dp[n];
}
printf("%d
",dp2[m]);
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[문제풀이] 루구 5662: 기념품원제 전송문 열거 현재 며칠째 d p i dp_i dpi는 오늘 원금이 i i i인 경우 오늘 사들이고 내일 팔면 가장 많은 이윤을 얻을 수 있다 즉, 제목의 뜻을 바꾸어 pi+1, j-3-pi, jp 를{i+1,j...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
