HDU 1244 DP
4376 단어 HDU
우리는 한 줄의 숫자를 여러 개의 확정 개수의 연속 단락으로 나누어 모든 단락의 최대 값을 얻어야 한다
dp[i][j]수 그룹을 정의하면 전 j개 수에서 i개 세그먼트를 채우면 얻을 수 있는 최대 값을 표시합니다
그러면 이 문제에서 한 단락 한 단락은 반드시 뽑혀야 한다는 뜻이죠.
얻을 수 있는 전제는 j>=cnt[i]//전 i단의 숫자 개수 총계를 나타낸다
sum[i]는 이전 i개의 숫자의 합을 나타낸다
우리는 두 가지 상황으로 나눌 수 있는데, 하나는 i단이 j호 숫자로 끝나는 것이다
dp[i-1][j-l[i]]+sum[j]-sum[j-l[i]] 획득
두 번째는 j로 끝나지 않아요.
dp[i][j-1] 획득
저희가 항상 그중에서 최대치를 뽑았으면 좋겠어요.
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int INF = 200000000;
const int M = 22;
const int N = 1005;
int dp[M][N] , l[M] , a[N] , cnt[M] , sum[N];
int main()
{
int m , n;
while(scanf("%d" , &n) , n){
scanf("%d" , &m);
for(int i = 1 ; i<=m ; i++){
scanf("%d" , l+i);
cnt[i] = cnt[i-1] + l[i];
}
for(int i = 1 ; i<= n ; i++){
scanf("%d" , a+i);
sum[i] = sum[i-1] + a[i];
}
memset(dp , 0 , sizeof(dp));
/*
， AC
dp 0， ，
for(int i = 1 ; i<= m ; i++)
for(int j = cnt[i] ; j<=n ; j++)
dp[i][j] = -INF;
*/
for(int i = 1 ; i<= m ; i++)
for(int j = cnt[i] ; j<=n ; j++){
dp[i][j] = max(dp[i-1][j-l[i]] + sum[j] - sum[j-l[i]] , dp[i][j-1]);
}
printf("%d
" , dp[m][n]);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
