poj 3661 dp(Running)

1391 단어
제목:Bessie는 달리기 시합에 참가하여 매 분마다 뛰거나 휴식을 선택할 수 있으며, 동시에 매 분마다 뛰면 뛸 수 있는 거리를 제시한다. 뛰면 피로도가 1이 증가한다.쉬면 피로도 1 감소;또한 피로도는 m를 초과해서는 안 된다.달리기를 마친 후 피로도는 반드시 0이어야 하며, 조건을 만족시키려면 가장 멀리 뛸 수 있다.
사고방식: 나는 직관적으로 생각하는 3차원 dp에 따른다.dp[i][j][0]는 i분 이후 피로도가 j이고 i분 휴식의 최대치를 나타낸다.dp[i][j][1]은 i분 이후 피로도가 j이고 i분 달리기의 최대치를 나타낸다.복잡도는 O(nm)로 A가 가능하다.
그러면 dp[i][j][1]=dp[i-1][j-1][1]+s[i], j>0
dp[i][0][1] = max(max(dp[i-1][1][0],dp[i-1][1][1]),dp[i-1][0][1]),  j=0
dp[i][j][0] = max(dp[i-1][j+1][0] , dp[i-1][j+1][j]).
공식적인 문제풀이는 1차원 수조만 사용했고 dp의 사고방식이기도 하다.만나다http://blog.csdn.net/power721/article/details/5841795)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
using namespace std;
#define clc(s,t) memset(s,t,sizeof(s))
#define INF 0x3fffffff
#define N 10005
int dp[N][505][2];
int s[N];
int n,m;
int main(){
    int i,j;
    scanf("%d %d",&n,&m);
    for(i = 1;i<=n;i++)
        scanf("%d",&s[i]);
    clc(dp,0);
    for(i = 1;i<=n;i++){
        dp[i][0][1] = max(max(dp[i-1][1][0],dp[i-1][1][1]),dp[i-1][0][1]);
        for(j = 1;j<=m;j++){
            dp[i][j][1] = dp[i-1][j-1][1]+s[i];
            dp[i][j][0] = max(dp[i-1][j+1][0],dp[i-1][j+1][1]);
        }
    }
    printf("%d
",dp[n][0][1]); }

좋은 웹페이지 즐겨찾기