浅谈dp（1）

dp，基本是所有$oier$前期的噩梦。

一、基本思想

dp，全称动态规划。

可以理解成把答案看成一个状态，然后用前面的状态算出这个状态。

可能有点抽象？

斐波那契数列问题就是一个简单的dp。

我们可以把计算时的$Feb_i$看成状态，表示的是 斐波那契数列第$i$项的值。

然后计算的方式就是$Feb_i = Feb_{i - 1} + Feb_{i - 2}$

我们把计算$Feb_i$的这个东西，称作 状态转移方程。

而这个计算的过程，就叫做 状态转移。

计算这个状态的过程可以打一个比方：

$Acwing$网校需要定期给班主任交一些费用维护$Acwing$。

而班主任又需要再交给年级主任，年级主任交给校长，也就是@yxc老师，接着会被用于网站维护。

所以所有钱会一点点汇聚到一起，然后变成更大更快的服务器。。。

这个过程就很类似与dp。

举个例子，数字三角形，就是一类dp问题。

数字三角形

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数$n$，表示数字三角形的层数。

接下来$n$行，每行包含若干整数，其中第 $i$ 行表示数字三角形第 $i$ 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

$1≤n≤500,$
$−10000≤$三角形中的整数$≤10000$

输入样例：

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例：

30

动态规划一般分为两部分： 状态表示和 状态计算。

状态表示指的是我们看看$f$数组表示的是什么。

状态计算指的是$f$数组的计算方法。

状态表示可以理解成一个 化零为整的过程。

状态计算可以理解成一个 化整为零的过程。

我们可以来分析一下。

给大家一些动态规划的提示：

1. dp没有什么指定的模板
2. dp有一些套路，记住可以好一些。
3. dp一定要自己想

状态表示

一般互道这种上的题目，我们$f$数组表示的是位置。

也就是说$f[i][j]$表示位置为${i, j}$的位置所得到的答案。

状态计算

状态计算的时候就是一个集合划分的过程。

可以分成从左上走来的和右上走来的。

$f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);$

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            scanf("%d", &a[i][j]);

    for(int i = 0; i <= n;i  ++)
        for(int j = 0; j <= i + 1; j ++)
            f[i][j] = -INF;

    f[0][0] = a[0][0];
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);

    int res = 0;
    for(int i = 1; i <= n;i ++) res = max(res, f[n][i]);

    printf("%d", res);

    return 0;
}

blog水完了，基本4月份以前很少更新了，大部分时候都去刷CF了，偶尔会更新一些dp的

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m;
int f[N];
int main()
{
    cin >> n >> m;
    f[0] = 1;
    for(int i = 0; i < n; i ++)
    {
        int v;
        cin >> v;
        for(int j = m; j >= v; j --) f[j] += f[j - v];
    }
    cout << f[m] << endl;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
using namespace std;
const int N = 111110;
int n, m, v[N], w[N];
int f[N];
int main()
{
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= n; i ++)
    {
        int a,b,s;cin>>a>>b>>s;
        int k = 1;
        while(k <= s)
        {
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if(s > 0)
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;
    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
}

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int h[N];
bool check(int mid)
{
    for(int i = 1; i <= n; i ++)
    {
        mid = mid * 2 - h[i];
        if(mid < 0) return false;
        if(mid >= 1e5) return true;
    }
    return true;
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> h[i];
    int l = 0, r = 1e5;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int h[N];
bool check(int mid)
{
    for(int i = 1; i <= n; i ++)
    {
        mid = mid * 2 - h[i];
        if(mid < 0) return false;
        if(mid >= 1e5) return true;
    }
    return true;
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> h[i];
    int l = 0, r = 1e5;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int h[N];
bool check(int mid)
{
    for(int i = 1; i <= n; i ++)
    {
        mid = mid * 2 - h[i];
        if(mid < 0) return false;
        if(mid >= 1e5) return true;
    }
    return true;
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> h[i];
    int l = 0, r = 1e5;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int h[N];
bool check(int mid)
{
    for(int i = 1; i <= n; i ++)
    {
        mid = mid * 2 - h[i];
        if(mid < 0) return false;
        if(mid >= 1e5) return true;
    }
    return true;
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> h[i];
    int l = 0, r = 1e5;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    int cnt = 0;
    int sum = 0;
    while(cin >> n, n)
    {
        if(n == 1)
        {
            sum ++;
            cnt = 0;
        }
        else if(n == 2)
        {
            cnt += 2;
            sum += cnt;
        }
    }
    cout << sum << endl;
    return 0;
}