【动态规划+贪心】

对于这个问题，能闪现肯定会闪现，这是显然的。

但是有时候不能闪现，于是我们有两个选择，跑步和休息。

但是这两玩意谁也说不准谁更大，于是这两个我们都要维护。

发现能量足够的情况下，先跑步再闪现和先闪现再跑步本质相同，所以我们可以直接记下只闪现的位置，然后跑步的位置可以由上一秒闪现后再继续走。然后对于跑步贪心取最大即可。

CPP

#include <bits/stdc++.h>
using namespace std;

int m, s, t;
int main()
{
    cin >> m >> s >> t;
    int zoulu = 0, shan = 0;
    for(int i = 1; i <= t; i++)  //枚举时间
    {
        zoulu += 17;  //正常走
        if(m >= 10)  //如果魔法值够了就可以使用技能
        {
            shan += 60;
            m -= 10;  //减去魔力值
        }
        else m += 4;  //恢复魔力值

        if(shan > zoulu) zoulu = shan;  //如果瞬移比走快就更新
        if(zoulu >= s)
        {
            cout << "Yes" << endl << i;
            return 0;
        }
    }
    cout << "No" << endl << zoulu;
    return 0;   
}

2.P1077 [NOIP 2012 普及组] 摆花

P1077题解

CPP

#include <bits/stdc++.h>
using namespace std;

const int N = 105, mod = 1e6 + 7;
int n, m, a[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];

    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k <= min(j, a[i]); k++)
                f[i][j] = (f[i][j] + f[i-1][j-k]) % mod;
    cout << f[n][m] << endl; 
    return 0; 
}

【动态规划】普及~省选的dp题题解

文章操作

题单

「0x1 暴力dp」

1.P1095 守望者的逃离

2.P1077 [NOIP 2012 普及组] 摆花

相关推荐

评论

【动态规划】普及~省选的dp题题解