题意:要参加一个比赛,要想赢一场比赛,自身等级必须大于等于对手的等级,初始等级为L,比赛场数N.主人公可以吃药,吃了药之后等级临时变成L + 1持续X场,X场之后会变成0级并且持续Y场后又变回初始等级L.求最多能赢多少场.
设dp[i][0]为在第i场吃药到最后最多能赢多少场,dp[i][1]为在第i场不吃药到最后最多能赢多少场.
1)dp[i][0] = [i, X + Y - 1]的赢得场数+max(dp[i + X + Y][0], dp[i + X + Y])
2)dp[i][1] = max([i, k]的赢得场数 + dp[k + 1][0]) i<=k<=N
从后往前推.
#include#include #include using namespace std; const int MAX = 105; int main(int argc, char const *argv[]){ int dp[MAX][2]; int level[MAX]; int L, N, X, Y; while(scanf("%d%d%d%d", &L, &N, &X, &Y) == 4){ memset(dp, 0, sizeof(dp)); for(int i = 1; i <= N; ++i){ scanf("%d", &level[i]); } for(int i = N; i >= 1; --i){ //case 1: use the Level Upper before round i dp[i][0] = 0; int wins = 0; for(int k = i; k < i + X && k <= N; ++k){ if(L >= level[k] || (L < 5 && L + 1 >= level[k])){//can't use when at level 5 or greater ++wins; } } for(int k = i + X; k < i + X + Y && k <= N; ++k){ if(0 >= level[k]){ ++wins; } } dp[i][0] = wins + max(dp[min(i + X + Y, N + 1)][0], dp[min(i + X + Y, N + 1)][1]); //case 2: do not use the Level Upper before round i dp[i][1] = 0; wins = 0; for(int k = i; k <= N; ++k){ if(L >= level[k]){ wins++; } dp[i][1] = max(dp[i][1], wins + max(dp[k + 1][0], dp[k + 1][1])); } } printf("%d\n", max(dp[1][0], dp[1][1])); } return 0; }