代码笔记_动态规划

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

代码笔记_动态规划

作者：

zqiceberg , 2020-01-15 23:01:55 , 所有人可见 , 阅读 1211

1

6

`线性DP-数字三角形模型`

AcWing 898. 数字三角形

#include <iostream>
#include <algorithm>

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++)  //每行最右边的点，是没有右上方的点，要初始化i + 1
            f[i][j] = -INF;

    f[1][1] = a[1][1];
    for (int i = 2; 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 = -INF;
    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);

    printf("%d\n", res);
    return 0;
}

AcWing 1015. 摘花生

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int w[N][N];
int f[N][N];

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j<= m; j++)
                scanf("%d", &w[i][j]);

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

        printf("%d\n", f[n][m]);
    }

    return 0;
}

AcWing 1018. 最低通行费

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, INF = 1e9;

int n;
int w[N][N];
int f[N][N];

int main()
{
    scanf("%d", &n);

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

    for (int i = 1; i <= n; i++)
        for (int j= 1; j <= n; j++)
            if (i == 1 && j == 1) f[i][j] = w[i][j];
            else
            {
                f[i][j] = INF;
                if (i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);
                if (j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);
            }

    printf("%d\n", f[n][n]);

    return 0;
}

AcWing 1027. 方格取数

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
int w[N][N];
int f[N * 2][N][N];

int main()
{
    scanf("%d", &n);

    int a, b, c;
    while (cin >> a >> b >> c && a || b || c) w[a][b] = c;

    for (int k= 2; k <= n + n; k++)
        for (int i1 = 1; i1 <= n; i1++)
            for (int i2 = 1; i2 <= n; i2++)
            {
                int j1 = k - i1, j2 = k - i2;
                if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
                {
                    int t = w[i1][j1];
                    if (i1 != i2) t += w[i2][j2];

                    int &x = f[k][i1][i2];  //f[k][i1][i2]太长了，用一个引用来表示
                    x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);  //下下
                    x = max(x, f[k - 1][i1 - 1][i2] + t);  //下右
                    x = max(x, f[k - 1][i1][i2 - 1] + t);  //右下
                    x = max(x, f[k - 1][i1][i2] + t);      //右右
                }
            }

    printf("%d", f[n + n][n][n]);

    return 0;
}

AcWing 275. 传纸条

#include <iostream>

using namespace std;

const int N = 55;

int n,m;
int g[N][N];
int f[N * 2][N][N];

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

    for (int k = 2; k <= n + m; k++)
        for (int i = max(1, k - m); i <= n && i < k; i++)
            for (int j = max(1, k - m); j <= n && j < k; j++)
                for (int a = 0; a <= 1; a++)
                    for (int b = 0; b <= 1; b++)
                    {
                        int t = g[i][k - i];
                        if (i != j || k == 2 || k == n + m)
                        {
                            t += g[j][k - j];
                            f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] + t);
                        }
                    }

    cout << f[n + m][n][n] << endl;  //f(k, x1, x2)

    return 0;
}

`线性DP-最长上升子序列模型`

AcWing 895. 最长上升子序列

1≤N≤1000，
−109≤数列中的数≤109

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]); //下标从1开始

    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }

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

    printf("%d\n", res);

    return 0;
}

AcWing 896. 最长上升子序列 II

1≤N≤100000，
−109≤数列中的数≤109

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N]; //不同长度下，所有上升子序列结尾的最小值

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

    int len = 0;
    q[0] = -2e9;
    for (int i = 0; i < n; i++)  //二分出来小于某个数的最大的数
    {                            //二分出来小于a[i]的最大的数  
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);  //r找的是能接到哪个数的后面
        q[r + 1] = a[i]; //r是小于a[i]的最后一个数，r+1 是大于等于a[i]的
    }

    printf("%d\n", len);

    return 0;
}

AcWing 897. 最长公共子序列

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j])
                f[i][j] = max(f[i][j], f[i  -1][j - 1] + 1);
        }
    printf("%d\n", f[n][m]);

    return 0;
}

AcWing 1016. 最大上升子序列和

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1010;

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

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

    for (int i = 1; i <= n; i++)
    {
        f[i] = a[i];
        for (int j = 1; j < i; j++)
            if (a[j]  < a[i])
                f[i] = max(f[i], f[j] + a[i]);
    }

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

    printf("%d\n", res);

    return 0;
}

AcWing 1012. 友好城市

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

int n;
PII q[N];
int f[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &q[i].first, &q[i].second);
    sort(q, q + n);  //按first进行排序

    int res=  0;
    for (int i = 0; i < n;i++)
    {
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (q[i].second > q[j].second)  //第一个点有序，第二点也要有序，否则两条桥梁就会交叉
                f[i] = max(f[i], f[j] + 1);

        res = max(res, f[i]);        
    }

    printf("%d\n", res);

    return 0;
}

AcWing 1010. 拦截导弹

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int q[N];
int f[N], g[N];

int main()
{
    while (cin >> q[n]) n++;

    int res = 0;
    for (int i = 0; i < n; i++)
    {
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (q[j] >= q[i])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

    cout << res << endl;

    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        int k = 0;   
        while (k < cnt && g[k] < q[i]) k++; //没有遍历完所有序列，当前序列的结尾是小于当前数的
        g[k] = q[i];
        if (k >= cnt) cnt++;
    }

    cout << cnt << endl;

    return 0;
}

AcWing 187. 导弹防御系统

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;

int n;
int q[N];
int up[N], down[N];
int ans;

void dfs(int u, int su, int sd) //当前枚举到的第几个数，当前上升子序列的个数，当前下降子序列的个数
{
    if (su + sd >= ans) return;
    if (u == n)
    {
        ans = su +  sd;
        return;
    }

    //情况1 将当前数放到上升子序列中
    int k = 0;
    while (k < su && up[k] >= q[u]) k++;
    int t = up[k];   //现场备份一下
    up[k] = q[u];
    if (k < su) dfs(u + 1, su, sd);
    else dfs(u + 1, su + 1, sd);  //开辟一个新的上升子序列
    up[k] = t;  // 恢复现场

    //情况2 将当前数放到下降子序列中
    k = 0;
    while (k < sd && down[k] <= q[u]) k++;
    t = down[k];
    down[k] = q[u];
    if (k < sd) dfs(u + 1, su, sd);
    else dfs(u + 1, su, sd + 1);
    down[k] = t;
}

int main()
{
    while (cin >> n, n)  //输入处理方式
    {
        for (int i = 0; i < n; i++) cin >> q[i];

        ans = n;
        dfs(0, 0, 0);

        cout << ans << endl;
    }

    return 0;
}

AcWing 902. 最短编辑距离
AcWing 899. 编辑距离
AcWing 1017. 怪盗基德的滑翔翼
AcWing 1014. 登山
AcWing 482. 合唱队形

`背包模型`

AcWing 2. 01背包问题

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

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

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];  // 右边集合为空，不包含i
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;

    return 0;
}

二维优化到一维

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
//int f[N][N];
int f[N];   
//计算f[i]这一层，只用到了f[i-1]这一层的数据，用滚动数组
//然后f[i][j - v[i]]都是用到小于j的，不会用到j右侧的

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

    for (int i = 1; i <= n; i++)
        //for (int j = v[i]; j <= m; j++)
        for (int j = m; j >= v[i]; j--)
        {
            //f[i][j] = f[i - 1][j];  // 右边集合为空，不包含i
            //f[j] = f[j];
            //if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            //f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            //第i层算的是f[i][j]
            //f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            // f[i - 1][j - v[i]]是严格小于j的，从小到大枚举的
            //计算f[j - v[i]], 但他在j层之前第i层已经被计算过了，
            //那么f[j - v[i]]其实是第i层的j - v[i], 等价于f[i][j - v[i]]

            //这与我们的刚才的二维里的状态计算不一致，刚才实际应该是f[i - 1][j - v[i]]
            //若j从大到小枚举，算f[j]的时候，f[j - v[i]]还没有被更新过，存的就是f[i - 1][j - v[i]]
            //这样就和二维的状态转移方程等价了

        }

    //cout << f[n][m] << endl;
    cout << f[m] << endl;

    return 0;
}

AcWing 3. 完全背包问题

第一种

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

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

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k *v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);

    cout << f[n][m] << endl;

    return 0;
}

第二种

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

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

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }

//            for (int k = 0; k *v[i] <= j; k++)
//                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);

    cout << f[n][m] << endl;

    return 0;
}

第三种

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

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

    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= m; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

//            for (int k = 0; k *v[i] <= j; k++)
//                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);

    cout << f[m] << endl;

    return 0;
}

AcWing 4. 多重背包问题

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);

    cout << f[n][m] << endl;

    return 0;
}

AcWing 5. 多重背包问题 II

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25000, M = 2010;

int n, m;
int 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] << endl;

    return 0;
}

AcWing 9. 分组背包问题

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        for (int j = 0; j < s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 0; j--)
            for (int k = 0; k < s[i]; k++)
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;

    return 0;    
}