代码

luoguP1541:NOIP2010提高组:乌龟棋

题目:https://www.luogu.org/problem/show?pid=1541
题意:
每个格子有一个值,可以有限定次数地走1,2,3,4步,求经过的格子的值总和
做法:
一开始想到的自然是n*k1*k2*k3*k4的DP,五维数组,内存可以滚动,但是时间复杂度...
后来发现其实可以直接忽略步数,直接开四维
dp[i][j][k][l]:分别用了几张卡片取得的值

#include<cstdio>
#include<cstring>
#define MAXC 41
#define MAXN 351
using namespace std;
int n, m;
int dp[MAXC][MAXC][MAXC][MAXC];
int card[4];
int a[MAXN];

int max(int a, int b){
	return a > b? a: b;
} 

int main(){
    memset(a, 0, sizeof(a));
    memset(dp, 0, sizeof(dp));
    memset(card, 0, sizeof(card));
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++){
        int t;
        scanf("%d", &t);
        card[--t]++;
    }
    for (int i = 0; i <= card[0]; i++)
        for (int j = 0; j <= card[1]; j++)
            for (int k = 0; k <= card[2]; k++)
                for (int l = 0; l <= card[3]; l++)
                    for (int p = 0; p <= 3; p++){
                        if(p == 0 && i > 0) dp[i][j][k][l] = max(dp[i - 1][j][k][l] + a[i + j * 2 + k * 3 + l * 4], dp[i][j][k][l]);
                        else if(p == 1 && j > 0) dp[i][j][k][l] = max(dp[i][j - 1][k][l] + a[i + j * 2 + k * 3 + l * 4], dp[i][j][k][l]);
                        else if(p == 2 && k > 0) dp[i][j][k][l] = max(dp[i][j][k - 1][l] + a[i + j * 2 + k * 3 + l * 4], dp[i][j][k][l]);
                        else if(p == 3 && l > 0) dp[i][j][k][l] = max(dp[i][j][k][l - 1] + a[i + j * 2 + k * 3 + l * 4], dp[i][j][k][l]);
                    }
    printf("%d", dp[card[0]][card[1]][card[2]][card[3]] + a[0]);
}

b-a
我还没有学会写个人说明!
查看“b-a”的所有文章 →

Leave a Reply

Your email address will not be published. Required fields are marked *

相关推荐