动态规划

zhubian · 2023-03-19 14:45:59 · 个人记录

动态规划

核心思路:

设定状态
边缘情况
状态转移

例题

NKOJ

设定状态:f[i][j]代表到达该点的最大值(max)
边缘情况:f[n][j]=a[n][j]
状态转移:f[i][j]=a[i][j]+max(f[i+1][j],f[i+1][j+1])
答案 f[1][1]

#include<cstdio>
using namespace std;
#define ll int
const ll N = 1e3 + 10;
ll arr[N][N];
ll n;
ll max(ll a,ll b){
    if(a>b) return a;
    return b;
}
int main() {
    scanf("%d",&n);
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= i; j++) {
            scanf("%d", &arr[i][j]);//dp数组与原数组可合并
        }
    }
    for (ll i = n - 1; i >= 1; i--) {
        for (ll j = 1; j <= i; j++) {
            arr[i][j] += max(arr[i + 1][j], arr[i + 1][j + 1]);//状态转移
        }
    }
    printf("%d", arr[1][1]);//答案
    return 0;
}

NKOJ

设定状态:f[i]代表以a[i]结尾的最大连续子序列的和(max)
边缘情况:f[1]=a[1]

状态转移:

当f[i-1]<=0时,f[i]=a[i]

否则f[i]=a[i]+f[i-1]

整理得:f[i]=max(a[i]+f[i-1],a[i])

答案 f[]数组的最大值

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=3e3+10;
ll a[N],f[N];
ll n,maxn;
int main()
{
cin>>n;
for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
f[1]=a[1],maxn=f[1];//初始化
for(ll i=2;i<=n;i++){
    f[i]=max(a[i]+f[i-1],a[i]);//状态转移
    maxn=max(maxn,f[i]);
}
printf("%lld",maxn);
return 0;
}

另类技巧(线段树)

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
const ll N = 1e6 + 10;

ll n, m, maxn = INT32_MIN;
ll a[N];

struct seg {
    ll l, r, sum;
} tree[N * 4];

void pushup(ll x) { //求和
    tree[x].sum = tree[x * 2].sum + tree[x * 2 + 1].sum;
}

void build(ll x, ll l, ll r) { //赋值
    tree[x].l = l;
    tree[x].r = r;
    if (l == r) {
        tree[x].sum = a[l];
        return ;
    }
    ll mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    pushup(x);
}

ll query(ll x, ll l, ll r) { //查询
    if (l <= tree[x].l && tree[x].r <= r) return tree[x].sum;
    ll mid = (tree[x].l + tree[x].r) / 2;
    ll sum = 0;
    if (l <= mid) sum += query(x * 2, l, r);
    if (mid < r) sum += query(x * 2 + 1, l, r);
    return sum;
}

void modify(ll x, ll p, ll k) { //更新
    if (tree[x].l == tree[x].r && tree[x].l == p) {
        tree[x].sum += k;
        return ;
    }
    ll mid = (tree[x].l + tree[x].r) / 2;
    //printf("%lld",mid);
    if (p <= mid) modify(x * 2, p, k);
    else modify(x * 2 + 1, p, k);
    pushup(x);
    return ;
}

int main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    build(1, 1, n);
    for (ll i = 0; i < n; i++) {
        for (ll j = 1; j + i <= n; j++) {
            ll st = j, ed = j + i;
            maxn = max(maxn, query(1, st, ed));
        }
    }
    printf("%lld", maxn);
    return 0;
}

NKOJ

设定状态:f[i]代表到达i点时乘车费用的最小值(min)
边缘情况:f[1]=a[1]
状态转移:f[i] = min(f[i], f[i - j] + a[j])(j<=i)
答案:f[n]

注意:求最小值时可能会被边界影响

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e2 + 10, M = 15;
ll a[M], f[N], n;
int main() {
    memset(f, 0x7f, sizeof f);//避免边界情况
    for (ll i = 1; i <= 10; i++) scanf("%lld", &a[i]);
    cin >> n;
    f[1] = a[1];
    f[0] = 0;//初始化
    for (ll i = 2; i <= n; i++) {
        for (ll j = 1; j <= 10; j++) {
            if (i - j < 0) break;//避免越界
            f[i] = min(f[i], f[i - j] + a[j]);
        }
    }
    printf("%lld", f[n]);
    return 0;
}

NKOJ

设定状态:
$f2[i]$表示从$i-n$中的最长下降子序列的长度(maxn)
边缘情况:f1[i]=f2[i]=1
状态转移:
f1[i]=max(f1[i],f1[j]+1) (j<i) (a[i]>a[j]) f1[i]=max(f1[i],f1[j]+1) (j>i) (a[i]>a[j])
答案:n-(max(f1)+max(f2)-1)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e2 + 10;
ll a[N], f1[N], f2[N];
ll n, maxn = INT32_MIN;
int main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (ll i = 1; i <= n; i++) f1[i] = 1, f2[i] = 1;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j < i; j++)
            if (a[i] > a[j]) f1[i] = max(f1[i], f1[j] + 1);//最长上升子序列
    for (ll i = n; i >= 1; i--)
        for (ll j = n; j > i; j--)
            if (a[i] > a[j]) f2[i] = max(f2[i], f2[j] + 1);//最长下降子序列
    for (ll i = 1; i <= n; i++) {
        maxn = max(maxn, f1[i] + f2[i] - 1);//求最值
    }
    printf("%lld", n - maxn);
    return 0;
}

NKOJ

贪心可求得每一列的最大值,把二维数组压缩为一维数组

此后求该数组的最大连续子序列

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e4 + 10;
ll f[N], a[N];
ll n, m, tmp, maxn = INT32_MIN, ans;
int main() {
    for (ll i = 0; i < N; i++) a[i] = INT32_MIN;
    cin >> m >> n;
    n--;
    for (ll i = 1; i <= m; i++) {
        for (ll j = 1; j <= n; j++) {
            scanf("%lld", &tmp);
            a[j] = max(a[j], tmp);//贪心
        }
    }
    for (int i = 1; i <= n; i++) {
        f[i] = max(a[i], f[i - 1] + a[i]);
        ans = max(ans, f[i]);//最大连续子序列
    }
    printf("%lld", ans);
    return 0;
}

NKOJ

设定状态: f[i][j]为到达此点的路径总数
状态转移: f[i][j] += (f[i][j - 1] + f[i - 1][j])

需要判断这个点会不会被马吃

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll qp[25][25];
ll n, m;
ll sx, sy;
bool cirl[25][25];//检查该点是否能走
ll dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
ll dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};//马的增量数组
int main()
{
    cin >> n >> m >> sx >> sy;
    cirl[sx + 1][sy + 1] = 1;
    for (ll i = 0; i < 8; i++) {
        cirl[sx + dx[i] + 1][sy + dy[i] + 1] = 1;
    }
    qp[1][1] = 1 - cirl[1][1];//出发点是否能走
    for (ll i = 1; i <= n + 1; i++) {
        for (ll j = 1; j <= m + 1; j++) {
            if (cirl[i][j] == 1) {
                qp[i][j] = 0;
            }
            else qp[i][j] += (qp[i][j - 1] + qp[i - 1][j]);//状态转移
        }
    }
    printf("%lld", qp[n + 1][m + 1]);
    return 0;
}

NKOJ

求一个序列的最长上升子序列和最长下降子序列O(nlogn)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll const N = 5e2 + 10;
ll a[N], f[N];
ll n;

void clear() {
    memset(f, 0, sizeof f);
    return ;
}

ll bs_LIS(ll l, ll r, ll target) {//二分
    while (l < r) {
        ll mid = l + (r - l) / 2;
        if (f[mid] > target) l = mid + 1;
        else r = mid;
    }
    return l;
}

ll bs_LNDS(ll l, ll r, ll target) {//二分
    while (l < r) {
        ll mid = l + (r - l) / 2;
        if (f[mid] >= target) r = mid;
        else l = mid + 1;
    }
    return l;
}

ll LIS() {//求最长上升子序列子序列的长度
    ll s = 1;
    f[s] = a[s];
    for (ll i = 2; i <= n; i++) {
        if (a[i] < f[s]) f[++s] = a[i];
        else f[bs_LIS(1, s, a[i])] = a[i];
    }
    return s;
}

ll LNDS() {//求最长下降子序列子序列的长度
    ll s = 1;
    f[s] = a[s];
    for (ll i = 2; i <= n; i++) {
        if (a[i] >= f[s]) f[++s] = a[i];
        else f[bs_LNDS(1, s, a[i])] = a[i];
    }
    return s;
}

int main() {
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++) scanf("%lld", &a[i]);
    printf("%lld\n", LIS());
    clear();//初始化
    printf("%lld\n", LNDS());
    return 0;
}

NKOJ

记忆化搜索

#include<bits/stdc++.h>
using namespace std;
int n, m;
const int N = 310;
int arr[N][N];
int dp[N][N];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int dfs(int x, int y)
{
    if (dp[x][y] != 0) return dp[x][y];
    dp[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int tempx = x + dx[i];
        int tempy = y + dy[i];
        if (tempx >= 1 && tempx <= n && tempy >= 1 && tempy <= m && arr[tempx][tempy] < arr[x][y]) {
            dp[x][y] = max(dp[x][y], dfs(tempx, tempy) + 1);
        }
    }
    return dp[x][y];
}
int res = -2147483647;
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            res = max(res, dfs(i, j));
        }
    }
    printf("%d", res);
    return 0;
}

NKOj

设定状态:f[i]代表价格为i时的方案总数(max)
状态转移:f[i]=f[i+a]+f[i+b]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1.1e6+10;
ll w,z,a,b,f[N];
int main(){
    cin>>w>>z>>a>>b;
    f[w]=1;
    for(ll i=w-1;i>=z;i--) f[i]=f[i+a]+f[i+b];
    printf("%lld",f[z]);
}