P1095 守望者的逃离

先用了贪心吧这个题 A 了，然后来考虑 dp 怎么做

先说贪心，其中 s1 表示走路的距离， s2 表示闪现了多远

s2 相当于只闪现，没蓝了就原地回蓝

但 s1 是两者兼备的，如果闪现的距离更远，就将 s1 覆盖为 s2

#include<iostream>
#include<cstdio>
#include<cstring>
//#define t time
#define NUM 100000010
#define ll long long
using namespace std;
ll m,s,t;
ll s1,s2,ans;
signed main(){
    ios::sync_with_stdio( false );
    cin >> m >> s >> t;
    while( s1 < s ){
        s1 += 17;
        if( m >= 10 ){
            s2 += 60;
            m -= 10;
        }else m += 4;
        s1 = max(s1,s2);
        ans++;
        if( ans >= t ) break;
    }
    if( s1 >= s ) printf( "Yes\n%lld",ans );
    else printf( "No\n%lld",s1 );
    return 0;
}

 上面是贪心的做法，dp 的话其实跟这个差不多

开一个 dp[i] 存第 i 秒的最远距离，

然后相当于贪心了，如果能闪现就闪现，跑步更优就跑步

还有一种做法，是看题解了，正儿八经的 dp

但是时间会超，想看就看看吧

设dp[i] [j] [1/0] 在第i秒时，魔法值为j，
0代表是由前一秒恢复得到的j，1代表不是恢复得到的j

则dp[i] [j] [0/1] 代表在第i秒时，魔法值为j，
是否是由恢复得到的j 所能跑到的最远距离

然后我们可以推出状态转移方程

先假设使用跳跃技能 dp[i] [j] [1]=max(dp[i-1] [j+10] [1]+60,dp[i-1] [j+10] [0]+60);

第i秒时魔法为j并且不是恢复的来的j（那么只能是由上一次消耗得来） 

所以为第i-1秒法力值为j+10秒时候0/1两个状态得来，
并且此种情况的条件为j+10<=m+1 为什么是m+1可以好好想一想

然后就是假设不用跳跃技能的最大值：
dp[i] [j] [1]=max(dp[i] [j] [1],dp[i-1] [j][1]+17); 
dp[i] [j] [1]=max(dp[i] [j] [1],dp[i-1][j] [0] +17);

然后就是0的情况，是由恢复法力得来的 j 
那么状态转移方程式为：
if(j>=4) dp[i] [j] [0]=max(dp[i-1][j-4] [1],dp[i-1] [j-4] [0]);

但是由于空间相当的大，我们要换成滚动数组

但是不开O2还是会T两个点

转移方程与解释

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int M,S,T,MAXN;
 4 int t;
 5 //dp[i][j][1/0] 在第i秒 ，魔法值为j  0代表是否是恢复得到的j，1代表不是恢复得到的j  是否跑的最远距离 
 6 int dp[2][1010][2]; 
 7 
 8 int main(){
 9     cin>>M>>S>>T;  //输入 
10     for(int i=1;i<=T;i++){      
11         for(int j=M;j>=1;j--){
12             if(j+10<=M+1) dp[i%2][j][1]=max(dp[(i-1)%2][j+10][1]+60,dp[(i-1)%2][j+10][0]+60); 
13             dp[i%2][j][1]=max(dp[i%2][j][1],dp[(i-1)%2][j][1]+17);
14             dp[i%2][j][1]=max(dp[i%2][j][1],dp[(i-1)%2][j][0]+17);
15             if(j>=4) dp[i%2][j][0]=max(dp[(i-1)%2][j-4][1],dp[(i-1)%2][j-4][0]);
16             MAXN=max(MAXN,dp[i%2][j][1]);
17             MAXN=max(MAXN,dp[i%2][j][0]);
18             if(MAXN>=S&&t==0) t=i; 
19         }
20     }
21     
22     if(MAXN<S){
23         cout<<"No"<<endl<<MAXN;
24     }
25     else{
26         cout<<"Yes"<<endl;
27         cout<<t;
28     }
29 }

代码

推荐这些文章：

Part 4.1 P1095 守望者的逃离【线性dp、思维】

原题链接：P1095 [NOIP2007 普及组] 守望者的逃离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题意：
守望者的跑步速度为 17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在 1s 内移动 60m，不过每次使用闪烁法术都会消耗魔法值 10 点。守望者的魔法值恢复的速度为 4 点每秒，只有处在原地休息状态时才能恢复。现在已知守望者的魔法初值 M，他所在的初始位置与岛的出口之间的距离 S，岛沉没的时间 T。你的任务是写一个程序帮...

maven：约定大于配置 可能会遇到配置问价无法被导出或者生效的问题 解决方法 ：build中配置resources 来防止资源导出失败的问题

maven：约定大于配置 可能会遇到配置问价无法被导出或者生效的问题 解决方法 ：build中配置resources 来防止资源导出失败的问题 <build> <resources> <resource> <directory>src/main/resources</directory> <includes> <include>**/*.properties</i...

【动态规划】【爬楼梯问题】931. 下降路径最小和

class Solution
{
public int minFallingPathSum( int[][] matrix )
{
int n = matrix.length;
int[][] dp = new int[n][n];

//对于第一行来说，每个坐标的值就是他的最小值
for(int i =0; i<n;i++)
{
dp[0][i] = matrix[0][i];
}
for(int i =1;i<n;i++)
...

【动态规划】【线性DP】 45. 跳跃游戏 II

45. 跳跃游戏 II - 力扣（LeetCode） (leetcode-cn.com)

下述均为对： 宫水三叶的题解的理解。原解释请直接 访问
我们知道最后一个点前面可能会有很多个点能够一步到达最后一个点。

也就是有 f[n−1]=min(f[n−k],...,f[n−3],f[n−2])+1
然后我们再来考虑集合 f[n−k],...,f[n−3],f[n−2] 有何特性。
不然发现其实必然有 f[n−k]<=...<=f[n−3]<=f[n−2]。
这个k 其实就是跳过来的步长，打个比方说， nums[2]=5, 那么从第2个台阶 就可以蹦五步 到达第7个台阶 ...

专题测试四 dp与贪心 A - QAQ

题目
"QAQ" is a word to denote an expression of crying. Imagine "Q" as eyes with tears and "A" as a mouth.
Now Diamond has given Bort a string consisting of only uppercase English letters of length n. There is a great number of "QAQ" in the string (Diamond is so cute!).
illustration by 猫屋 https...

木棍加工——线性dp、dilworth定理、最长上升子序列

P1233 木棍加工 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
读题可知我们要求的是将所有木棍分割成长度与宽度都是不上升子序列的序列个数。
既然是不上升子序列，那么我们就结构体排序一下。

1 bool cmp(const node&s1,const node&s2)
2 {
3 if(s1.l==s2.l)return s1.w>s2.w;
4 return s1.l>s2.l;
5 }

 
根据dilworth定理：
　　一个序列要最少分割为多少个不上升子序列的个数等于该序列最长上升子序列的长度。
　　注意：...

87. 扰乱字符串(leetcode)

87. 扰乱字符串

editorial:
典型的区间dp
定义\(dp[i][j][k]\)表示s1[i: i+k-1]是否是可以通过规则转化为s2[j: j+k-1]。
则动态规划的递推式为:\(dp[i][j][k]|=(dp[i][j][l] \land dp[i+l][j+l][k-l]) \lor (dp[i][j+k-l][l] \land dp[i+l][j][k-l]),k\in [1,k-1]\)
code:

class Solution {
public:
bool isScramble(string s1, string s2) {
int ...

P1926 小书童——刷题大军 题解

P1926 小书童——刷题大军

#include<iostream>
#include<algorithm>
using namespace std;
int dp[200];
int a[20],b[20],c[20];
int n,m,k,r;
int main()
{
cin>>n>>m>>k>>r;
for (int i=1;i<=n;i++)
{
cin>>c[i];
}
for (int i=1;i<=m;i++)
{
cin>>a[i];
}
f...

Maven解决静态资源过滤问题

在maven的pom文件配置中的相应节点顺序添加以下代码：
<build>
<resources>
<resource>
<directory>src/main/java</directory>
<includes>
<include>**/*.properties</include>
<include>**/*.xml</include>
</includes&g...

完全背包——洛谷 P1853 投资的最大效益

原题链接
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=15;
const ll U=1...