动态规划刷题总结

• • 1.骰子的点数
  • 3.守望者的逃离

题目分析：这个题目就是找方案数，对于一个骰子投掷n次会出现n-6*n种和，对于不太同的和，有多种组成方式，求每一种和有多少种方案
思路:用2维背包，第一维是次数，第二维是和，枚举这一次投掷出哪个数``
详细看代码：

class Solution
{
public:
    vector numberOfDice(int n)
    {
        vector>f(n+1,vector(6*n+1));
        f[0][0]=1;
        for(int i=1; i<=n; i++) //枚举次数
            for(int j=1; j<=6*i; j++) //枚举和
              for(int k=1;k<=6&&k<=j;k++)
                f[i][j]+=f[i-1][j-k];
        vectorp;
        for(int i=n;i<=6*n;i++)
            p.push_back(f[n][i]);
        return p;
    }
};

题目分析:规定时间内，能否走完距离，你有魔力，可以消耗10魔力用1s来走60，但是魔力1s恢复4，或者你可以1s跑17
思路：对于不用魔力，是1s跑17，然后只用魔力是1s跑60，但还需要2.5s来回复，相当于1s跑17.14，所以我们要尽可能用魔力跑，到后面不够时间回复的时候再用1s跑17
状态表示：f[i]表示前i秒最多跑的距离
详细看代码

#include
#define ll long long
#define PI 3.141592653589793
#define E 2.718281828459045
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define FO( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define lowbit(a) ((a)&-(a))
#define PII pair
#define ft first
#define sd second
typedef unsigned long long ull;
const ll mod=10007;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll Max=1e8+10;
using namespace std;
ll t,n,m,l,k;
ll ans;
ll f[Max];

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>t;
    for(ll i=1;i<=t;i++)
    {
        if(n>=10)
        {
            f[i]=f[i-1]+60;
            n-=10;
        }
        else 
        {  
            f[i]=f[i-1];
           n+=4;
        }
    }l=t+1;
    for(ll i=1;i<=t;i++)
    {
       f[i]=max(f[i],f[i-1]+17);
       if(f[i]>=m)
          l=min(l,i);
    }
     if(l==t+1)
     {
        cout<<"No"<
         cout<<"Yes"<