poj 2228 Naptime dp

1601 단어 time
이 문제의 상태는 비교적 좋다. dp[i][j]는 i시간대를 잤고 마지막에 j시간대의 최우수치를 잤다고 한다. 그러나 링을 처리해야 하는 경우 내 방법은 두 번으로 계산한다. 첫 번째는 링을 처리하지 않고 두 번째는 강제로 첫 번째 시간대에 잠을 자야 한다고 요구했다. 그리고 dp[m][n]+a[1]의 값이 더 좋은지 확인한다.
 
#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn=4e3+9;

int a[maxn],dp[maxn][maxn];



inline int max(int a,int b)

{

    if(a>b) return a;

    else return b;

}



int main()

{

//    freopen("in.txt","r",stdin);

    int n,m;

    while(scanf("%d %d",&n,&m)!=EOF)

    {



        for(int i=1;i<=m;i++)

        for(int j=1;j<=n;j++)

        dp[i][j]=0;

        for(int i=1;i<=n;i++)

        scanf("%d",&a[i]);

        for(int k=2,ret;k<=m;k++)

        {

            ret=0;

            for(int i=k;i<=n;i++)

            {

                dp[k][i]=max(ret,dp[k-1][i-1]+a[i]);

                ret=max(ret,dp[k-1][i-1]);

            }

        }

        int ans=0;

        for(int i=m;i<=n;i++)

        ans=max(dp[m][i],ans);



        for(int i=1;i<=m;i++)

        for(int j=1;j<=n;j++)

        dp[i][j]=0;



        dp[2][2]=a[2];

        for(int k=3,ret;k<=m;k++)

        {

            ret=0;

            for(int i=k;i<=n;i++)

            {

                dp[k][i]=max(ret,dp[k-1][i-1]+a[i]);

                ret=max(ret,dp[k-1][i-1]);

            }

        }

        if(m>=2)

        ans=max(ans,dp[m][n]+a[1]);

        cout<<ans<<endl;

    }

    return 0;

}


 

좋은 웹페이지 즐겨찾기