洛谷题单-动态规划的引入

动态规划的引入

P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles 题解
- 解法一: 从上往下推用dp
P1048 [NOIP2005 普及组] 采药题解
- 解法一: 一维01背包
P2196 [NOIP1996 提高组] 挖地雷题解
- 解法一: dfs暴搜
- 解法二: dp
- 解法三: 树形dp
P1434 [SHOI2002] 滑雪
- 解法一: 记忆化搜索
P4017 最大食物链计数
- 解法一: 记忆化搜索
- 解法二:拓扑排序
P1115 最大子段和题解
- 解法一: dp
P1802 5 倍经验日
- 解法一: dp 01背包
[NOIP2002 普及组] 过河卒题解

P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles 题解

解法一: 从上往下推用dp

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;
#define rint register int
inline void read(int &x)//读入优化 
{
    x=0;int w=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    x=x*w;
}
const int maxn=1000+10;
int n,a[maxn][maxn],ans; 
int main()
{
    read(n);
    for(rint i=1;i<=n;i++)
    {
        for(rint j=1;j<=i;j++)
        {
            read(a[i][j]);
            a[i][j]+=max(a[i-1][j-1],a[i-1][j]);//本题最重要的步骤 
            //a[i][j]代表从上往下到达i行j列这个点所能达到的和的最大值 
            ans=max(ans,a[i][j]);//在所有答案中找最大的（与在最底下一层找最大值是一样的）
        }
    }//边读入边计算，随手优化一下常数（其实只是懒得打for循环） 
    cout<<ans<<endl;
    return 0; 
}

P1048 [NOIP2005 普及组] 采药题解

记忆化搜索和动态规划如何联系起来
dp和记忆化搜索都是可以省略中间重复计算的值, 每个值只计算一遍

解法一: 一维01背包

#include "stdio.h"
#include "iostream"
using namespace std;
int w[105], val[105];
int dp[1005];
int main()
{
    int t,m,res=-1;    
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&w[i],&val[i]);
    }
    for(int i=1;i<=m;i++) 
    {
        for(int j=t;j>=0;j--) 
        {
            if(j>=w[i])
            {
                dp[j]=max(dp[j-w[i]]+val[i], dp[j]);
            }
        }
    }    
    printf("%d",dp[t]);
    return 0;
}

P2196 [NOIP1996 提高组] 挖地雷题解

解法一: dfs暴搜

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N = 22;
int a[N], g[N][N], b[N], ans[N], path[N];
int n, maxx, cnt;

//判断是否搜到头了
bool check(int cur)//false 代表还能继续往下挖, true代表到头了
{
    for(int i = 1; i <= n; ++ i)
        if (g[cur][i] && !b[i]) return false;
    return true;
}
void dfs(int cur, int step, int sum)
{
    if(check(cur))
    {
        if(sum > maxx)
        {
            maxx = sum;
            cnt = step;
            for (int i = 1; i <= step; ++ i) ans[i] = path[i];
        }
        return ;
    }
    
    for (int i = 1; i <= n; ++ i)
    {
        if (b[i] == 0 && g[cur][i])
        {
            b[i] = 1;
            path[step + 1] = i;//也可以用递归的方法去记录path 比如path[i] = j; 记录下答案的终点就行, 然后从终点递归往前遍历
            dfs(i, step + 1, sum + a[i]);
            b[i] = 0;
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    
    for (int i = 1; i < n; ++ i)
    {
        for (int j = i + 1; j <= n; ++ j)
         cin >> g[i][j];
    }
    for(int i = 1; i <= n; ++ i)
    {
        b[i] = 1;
        path[1] = i;
        dfs(i, 1, a[i]);
        b[i] = 0;
    }
    
    for (int i = 1; i <= cnt; ++ i) cout << ans[i] << " ";
    cout << endl;
    cout << maxx;
    return 0;
}

解法二: dp

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N = 22;
int g[N][N], f[N], ans[N], maxx, n, a[N], endpos;

void dfs(int x)
{
    if (ans[x] != 0) dfs(ans[x]);//递归
    cout << x << " ";
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    for (int i = 1; i < n; ++ i)
        for (int j = i + 1; j <= n; ++ j)
            cin >> g[i][j];
            
    f[1] = a[1];
    for (int i = 2; i <= n; ++ i)
    {
        f[i] = a[i]; 
        for (int j = i - 1; j > 0; --j)
            if (g[j][i] && f[i] < f[j] + a[i])
            {//站在i这个点遍历其他点j能否到i并且更新i, 因此是g[j][i]而不是g[i][j];
                f[i] = f[j] + a[i];
                ans[i] = j;// i 是从 j转移过来的
            }
        if (f[i] > maxx) 
        {
            maxx = f[i]; 
            endpos = i;
        }
    }
    
    dfs(endpos);
    cout << endl;
    cout << maxx;
    return 0;
}

解法三: 树形dp

这题展开是一个图, 图的话就可以联想到树形dp, 后面学树形dp的时候再去看看这题;
不知道为啥我这段代码会wa两个点

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 22, M = 502;
int h[N], ne[N], val[N], e[M], idx = 0;
int n, maxx, ans[N], startpos, dp[N], pre[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
//dp[i] 表示i节点的最大值
int dfs(int u, int fa)
{
    if (dp[u]) return dp[u];// 记忆化搜索
    for (int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if (v == fa) continue;
        dp[v] = dfs(v, u);//收集v节点的值
        if(dp[v] > dp[u]) //当前dp[u]还没有加上w[u], 直接比较就行,
        {
            dp[u] = dp[v];
            pre[u] = v;
        }
    }
    return dp[u] + val[u];
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> val[i];
    
    for (int i = 1; i < n; ++ i)
        for (int j = i + 1; j <= n; ++ j)
        {
            int x;
            cin >> x;
            if (x) add(i, j);
        }
    
    for (int i = 1; i <= n; ++ i)
    {
        memset(dp, 0, sizeof(dp));
        int tmp = dfs(i, 0);
        if (tmp > maxx)
        {
            maxx = tmp;
            startpos = i;
        }
    }
    
    while (startpos)
    {
        cout << startpos << " ";
        startpos = pre[startpos];
    }
    
    cout << endl << maxx;
    
    return 0;
}

P1434 [SHOI2002] 滑雪

解法一: 记忆化搜索

看了一些dp的做法(也没完全看出来, 感觉dp的写法也长得很想记忆化搜索), 觉得这道题还是一个搜索的做法, 但是记忆化搜索和dp思想很类似, 少部分dp和记忆化搜索的代码可以相互转化, 可能这样就可以和dp联系起来了把;详见下面这篇博客
记忆化搜索和动态规划如何联系起来

#include<iostream>
#include<string>
using namespace std;
const int N = 110;
int m, n;
int f[N][N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
int h[N][N];
int ans;

int dfs(int x, int y)
{
    if (f[x][y]) return f[x][y];//记忆化搜索
    f[x][y] = 1;
    for (int i = 0; i < 4; ++ i)
    {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx >= 0 && xx < n && yy >= 0 && yy < m && h[xx][yy] < h[x][y]) 
            f[x][y] = max(f[x][y], dfs(xx, yy) + 1);//记忆化搜索
    }
    
    return f[x][y];
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j) cin >> h[i][j];
    
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            ans = max(ans, dfs(i, j));
    cout << ans;
}

P4017 最大食物链计数

解法一: 记忆化搜索

读取数据的时候预先处理好哪些是食物链顶端的动物, 然后dfs这些动物就行了

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 5e5 + 10;
int n, m;
vector<int> eat[N];
int f[N], isNotTop[N];
int mod = 80112002, ans;
int dfs(int u)
{
    int res = 0;
    if (eat[u].size() == 0) return f[u] = 1;//记忆化搜索
    for (int i = 0; i < eat[u].size(); ++i)
    {
        int v = eat[u][i];
        if (!f[v]) res = (res + dfs(v)) % mod;
        else res = (res + f[v]) % mod;
    }
    return f[u] = res; //记忆化搜索
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; ++i)
    {
        
        int a, b;
        cin >> a >>b;
        eat[b].push_back(a);
        isNotTop[a] = 1;
    }
    for (int i = 1; i <= n; ++ i)
    {
        if (isNotTop[i] == 0) ans = (ans + dfs(i)) % mod;
    }
    cout << ans;
    return 0;
}

解法二:拓扑排序

拓扑排序: 把入度为0的节点删掉并且删掉其相关的边, 重复此步骤直到途中所有节点都删掉了, 节点删掉的顺序就是拓扑排序;
我觉得拓扑排序相关的算法就是在找到下一个入度为0的节点的时候执行相关操作
无后效性:无后向性是指以前出现状态和以前状态的变化过程不会影响将来的变化。
知乎上的问题
在这里插入图片描述

#include<iostream>
#include<cstring>
#include <queue>
using namespace std;
const int N = 6e3, M = 5e6 + 2;
int n, m, mod = 80112002;
int out[N], in[N];// in[b]表示b可以吃的物种数量, out[a]表示可以吃a的物种数量
int h[N], e[M], ne[M], idx;
int f[N], ans;
queue<int> q; 
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void topo()
{
    for (int i = 1; i <= n; ++ i)
    {
        if (in[i] == 0) 
        {
            q.push(i);
            f[i] ++;
        }
    }
    
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];
            f[v] = (f[v] + f[u]) % mod;
            in[v]--;
            if (in[v] == 0) 
            {
                q.push(v);
            }
        }
    }
}
int main()
{
    memset(h, -1, sizeof h);//这里很重要, 之前我不想memset , for循环中循环中断条件是i!=0, 但其实一开始 ne[idx] = h[a], h[a]的初始值就是0,导致循环只执行一次就没了
    cin >> n >> m;
    for (int i = 0; i < m; ++ i)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        out[a] ++ ;
        in[b] ++;
    }
    topo();
    for (int i = 1; i <= n; ++ i) 
        if (out[i] == 0)
            ans = (ans + f[i]) % mod;
    cout << ans;
}

P1115 最大子段和题解

解法一: dp

第一个数为一个有效序列
如果一个数加上上一个有效序列得到的结果比这个数大，那么该数也属于这个有效序列。
如果一个数加上上一个有效序列得到的结果比这个数小，那么这个数单独成为一个新的有效序列
在执行上述处理的过程中实时更新当前有效序列的所有元素之和并取最大值。

#include<iostream>
#include<cstring>
#include <queue>
using namespace std;
int ans = 1e-9, a, b, n;
int main()
{
    cin >> n;
    for (int i = 0; i < n; ++ i)
    {
        cin >> a;//a: 新的数; b: 上一个有效序列; ans: 找到最大的有效序列(即为答案)
        if (i == 0) b = a;
        else b = max(b + a, a);
        ans = max(ans, b);
    }
    cout << ans;
    return 0;
}

P1802 5 倍经验日

本题有两个决策:

上边那个循环是指剩余药水j>=use[i]时的决策，
而下边这个循环是指j<use[i]时的决策，此时j要满足j<use[i]，也就是j<=use[i]-1，所以用use[i]-1来给j赋值
有一个问题: 会不会一个重量j 对一个物体i既选择了win也选择了lose?
答案: 不会, 因为我们分类的时候对一个j要么>use[i]要么<use[i], 大于use[i]的时候, 要么选择win[i], 要么选择lose[i], 但是小于use[i]的时候, 只能选择lose[i]

解法一: dp 01背包

#include<iostream>
#include<cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int lose[N], win[N], use[N], f[N];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++ i)
    {
        cin >> lose[i] >> win[i] >> use[i];
    }
    
    for (int i = 0; i < n; ++ i)
    {
        for (int j = m; j >= use[i]; --j)//01背包优化成一维的都是 从后往前推, 为了防止一个物品被重复选择
        {
            f[j] = max(f[j] + lose[i], f[j - use[i]] + win[i]);//01背包状态转移方程, 选或不选
        }
        for (int j = use[i] - 1; j >= 0; -- j) 
        	f[j] += lose[i];
    }
    printf("%lld",5ll*f[m]);
    return 0;
}