ZOJ 3741 Eternal Reality

2230 단어
제목 링크: ZOJ 3741 Eternal Reality
dp.
이 문제는 내가 올라오자마자 dfs를 썼는데, 과연 초과했다.
자꾸
다른 사람의 코드와 사고방식을 보고서야 썼는데, 이 dp는 확실히 어렵지 않다.
dp[i][j]는 i라운드 경기를 의미하며, 최근 약을 먹은 것은 j라운드이고, j=0은 줄곧 약을 먹지 않았다는 뜻이다.
주의 제목에는 However, no one can achieve this level, even with the help of Level Upper(it has no effect on persons with super powers)가 있습니다.그래서 lv5는 약을 먹든 안 먹든 lv6를 못 말려요.
#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 100 + 10;
int dp[MAX_N][MAX_N];
int a[MAX_N];
int l,n,x,y;

int main()
{
    while(cin >> l >> n >> x >> y)
    {
        for(int i = 1;i <= n;i++)
            cin >> a[i];
        memset(dp,0,sizeof(dp));
        for(int i = 1;i <= n;i++)
        {
            for(int j = 0;j <= i;j++)
            {
                if(j == 0)
                {
                    dp[i][j] = dp[i - 1][j];
                    if(l >= a[i])
                        dp[i][j]++;
                }
                else if(i <= j + x - 1 && i != j)
                {
                    dp[i][j] = dp[i - 1][j];
                    if(l + 1 >= a[i] && a[i] <= 5)
                        dp[i][j]++;
                }
                else if(i > j + x - 1 && i <= j + x + y - 1 && i != j)
                {
                    dp[i][j] = dp[i - 1][j];
                    if(0 >= a[i])
                        dp[i][j]++;
                }
                else if(i == j)
                {
                    int last = max(0,j - ((i + x + y - 1) - i + 1));
                    for(;last >= 0;last--)
                        dp[i][j] = max(dp[i - 1][last],dp[i][j]);
                    if(l + 1 >= a[i] && a[i] <= 5)
                        dp[i][j]++;
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                    if(l >= a[i])
                        dp[i][j]++;
                }
            }
        }
        int _max = 0;
        for(int j = 0;j <= n;j++)
            _max = max(dp[n][j],_max);
        cout << _max << endl;
    }
    return 0;
}

좋은 웹페이지 즐겨찾기