动态规划 | Rainy2k

一些DP题目存档

[CF] k-Tree

寒假手速赛第一场

题意:…

时间复杂度: $O(n*k)$

思路:直接模拟，选或者不选，dp数组第一维为和，第二维为是否包含重量大于d的边

（考虑组合数做法？）

https://codeforces.com/group/GlRm4CeuZ9/contest/266331/problem/C

#include<bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int maxn = 1e5 + 5;
long long dp[maxn][3];
int main() {
    int n, k, d;
    scanf("%d%d%d", &n, &k, &d);
    dp[0][0] = 1;
    for (int i = 1; i <= n;i++) {
        for (int j = 1; j <= k;j++) {   
            if(i>=j) {
                if(j<d) {
                    dp[i][0] = (dp[i][0] + dp[i - j][0]) % mod;
                    dp[i][1] = (dp[i][1] + dp[i - j][1]) % mod;
                }
                else if(j>=d) {
                    dp[i][1] = (dp[i][1] + dp[i - j][0] + dp[i - j][1]) % mod;
                }
            }
        }
    }
    cout << dp[n][1] << endl;
}

操作集锦

https://ac.nowcoder.com/acm/contest/4853/C

题意

找到长度为k的本质不同的子序列的个数

思路

按照长度枚举

for (int i = 1; i <= n; i++) {
    int v = s[i] - 'a';
    pre[i] = pos[v];
    pos[v] = i;
}
for (int i = 1; i <= k; i++) {
    for (int j = 1; j <= n; j++) {
        if (!pre[j])
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1] + (i > 1 ? 0 : 1)) % mod;

        else
            dp[i][j] = (dp[i][j-1]+dp[i-1][j-1]-dp[i-1][pre[j]-1]+mod) % mod;
    }
}

代码 : https://xlorpaste.cn/gewr71

[CF] LCIS

寒假手速赛第一场

题意:求给定两个序列的公共最长子序列

时间复杂度: $O(n^2)$

思路:增加一个指针，一个记录路径的数组即可

https://codeforces.com/group/GlRm4CeuZ9/contest/266331/problem/D

#include<bits/stdc++.h>
using namespace std;

const int maxn = 500 + 5;

int a[maxn],s[maxn];
int dp[maxn], pre[maxn];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n;i++){
        scanf("%d", &a[i]);
    }
    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m;i++) {
        scanf("%d", &s[i]);
    }
    for (int i = 1; i <= n;i++) {
        int x = 0;
        for (int j = 1; j <= m; j++) {
            if(a[i]<s[j])
                continue;
            if(a[i]>s[j]) {
                if(dp[j]>dp[x]){
                    x = j;
                }
            }
            if(a[i] == s[j]) {
                if(dp[j]<dp[x]+1) {
                    dp[j] = dp[x] + 1;
                    pre[j] = x;
                }
            }
        }
    }
    int ans = 0;
    int t = 0;

    for (int i = 1; i <= m;i++) {
        if(dp[i]>dp[t]){
            ans = dp[i];
            t = i;
        }
    }
    printf("%d\n", ans);

    vector<int> v;
    while(t) {
        v.push_back(s[t]);
        t = pre[t];
    }

    int sz = v.size();
    for (int i = sz - 1; i >= 0;i--) {
        printf("%d", v[i]);
        if(i == 0) printf("\n");
        else printf(" ");
    }
}

[CF] Elevator

https://codeforces.com/group/GlRm4CeuZ9/contest/266331/problem/E

题意：某电梯可以承载4个人，上、下电梯均需要1s，上、下一层均需要1s，乘客按照排队顺序上电梯

给定每个乘客所在楼层和目标楼层，问送完所有乘客的最短时间

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2000 + 5;
const int inf = 0x3f3f3f3f;
int dp[maxn][10][10][10][10];
int x[maxn], y[maxn];
int n;
int dis(int x,int y) {
    return abs(x - y);
}
int dfs(int i,int cur,int a,int b,int c) {
    if(dp[i][cur][a][b][c])
        return dp[i][cur][a][b][c];
    int ans = inf;
    if(i>n) {
        if(!a&&!b&&!c)
            return 0;
        if(a)
            ans = min(ans, dfs(i, a, 0, b, c) + dis(cur, a) + 1);
        if(b)
            ans = min(ans, dfs(i, b, a, 0, c) + dis(cur, b) + 1);
        if(c)
            ans = min(ans, dfs(i, c, a, b, 0) + dis(cur, c) + 1);
        return dp[i][cur][a][b][c] = ans;
    }
        if(a)
            ans = min(ans, dfs(i, a, 0, b, c) + dis(cur, a) + 1);
        if(b)
            ans = min(ans, dfs(i, b, a, 0, c) + dis(cur, b) + 1);
        if(c)
            ans = min(ans, dfs(i, c, a, b, 0) + dis(cur, c) + 1);
        if(a&&b&&c) {
            ans = min(ans, dfs(i + 1, y[i], a, b, c) + dis(cur, x[i]) + dis(x[i], y[i]) + 2);
            ans = min(ans, dfs(i + 1, a, y[i], b, c) + dis(cur, x[i]) + dis(x[i], a) + 2);
            ans = min(ans, dfs(i + 1, b, a, y[i], c) + dis(cur, x[i]) + dis(x[i], b) + 2);
            ans = min(ans, dfs(i + 1, c, a, b, y[i]) + dis(cur, x[i]) + dis(x[i], c) + 2);
        }
        else {
            if(!a)
                ans = min(ans, dfs(i + 1, x[i], y[i], b, c) + dis(cur, x[i]) + 1);
            else if(!b)
                ans = min(ans, dfs(i + 1, x[i], a, y[i], c) + dis(cur, x[i]) + 1);
            else if(!c)
                ans = min(ans, dfs(i + 1, x[i], a, b, y[i]) + dis(cur, x[i]) + 1);   
        }
        return dp[i][cur][a][b][c] = ans;
}
int main() {
    scanf("%d", &n);
    for (int i = 1;i<=n;i++)
        scanf("%d%d", &x[i], &y[i]);
    printf("%d\n", dfs(1, 1, 0, 0, 0));
}

[CF] 状压 Marbles

https://codeforces.com/contest/1215/problem/E

#include<bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 4e5 + 100;
int a[maxn];
int tot;

long long pre[30][30], cnt[30];
long long dp[1 << 21];

map<int, int> mp;
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n;i++) {
        scanf("%d", &a[i]);
        if(!mp[a[i]]){
            mp[a[i]] = tot++;
        }
    }
    for (int i = 1; i <= n;i++) {
        int x = mp[a[i]];
        for (int j = 0; j < tot;j++) {
            pre[x][j] += cnt[j];
        }
        cnt[x]++;
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i < (1 << tot); i++) {
        for (int j = 0; j < tot;j++) {
            if(i&(1<<j)) {
                long long temp = 0;
                for (int k = 0; k < tot;k++) {
                    if(j!=k&&!(i&(1<<k))) {
                        temp += pre[j][k];
                    }
                }
                dp[i] = min(dp[i], dp[i ^ (1 << j)] + temp);
            }
        }
    }
    printf("%lld\n", dp[(1 << tot) - 1]);
}

[CF1216F] Wi-Fi

https://codeforces.com/contest/1216/problem/F

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
int a[maxn];
long long dp[maxn], tr[maxn << 2];


void update(int rt,int l,int r,int pos,long long v) {
    if(l==pos&&r==pos) {
        tr[rt] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if(pos<=mid) {
        update(rt << 1, l, mid, pos, v);
    }
    else {
        update(rt << 1 | 1, mid + 1, r, pos, v);
    }
    tr[rt] = min(tr[rt << 1], tr[rt << 1 | 1]);
}

long long query(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R) {
        return tr[rt];
    }
    int mid = (l + r) >> 1;
    long long ans = 1e18;
    if(L<=mid)
        ans = min(ans, query(rt << 1, l, mid, L, R));
    if(R>mid)
        ans = min(ans, query(rt << 1 | 1, mid + 1, r, L, R));
    return ans;
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n;i++) {
        scanf("%1d", &a[i]);
    }
    memset(tr, 0x3f, sizeof(tr));
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    update(1, 0, n, 0, 0);
    for (int i = 1; i <= n;i++) {
        if(a[i]==0)
            dp[i] = min(dp[i], dp[i - 1] + i);
        else {
            int x = min(i + k, n);
            int y = max(i - k - 1, 0);
            dp[x] = min(dp[x], query(1, 0, n, y, n) + i);
            update(1, 0, n, x, dp[x]);
        }
        dp[i] = min(dp[i], query(1, 0, n, i + 1, n));
        update(1, 0, n, i, dp[i]);
    }
    printf("%lld\n", dp[n]);
}

#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 2e5 + 100;
 
long long dp[maxn];
int f[maxn],a[maxn];
 
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n;i++) {
        scanf("%1d", &a[i]);
    }
    f[n + 1] = 2 * n + k;
    for(int i = n;i>=1;i--) {
        if(a[i]==1) {
            f[i] = i;
        }
        else {
            f[i] = f[i + 1];
        }
    }
 
    for(int i=1;i<=n;i++) {
        dp[i] = dp[i - 1] + i;
        int t = f[max(1, i - k)];
        if(t<=i+k) {
            dp[i] = min(dp[i], dp[max(1, t - k) - 1] + t);
        }
    }
    printf("%lld\n", dp[n]);
}

最短路

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
int n, k;
int a[maxn];
long long dis[maxn];
int vis[maxn];
struct edge{
    int to;
    long long v;
};
vector<edge> G[maxn];
struct node{
    int to;
    long long dis;
    bool operator<(const node& b)const
    {
        return dis>b.dis;
    }
};
void dijkstra(int s) {
    for (int i = 0; i <= n + 1;i++)
        dis[i] = 1e18;

    priority_queue<node> q;
    q.push((node){s, 0});
    dis[s] = 0;

    while(!q.empty()) {
        node t = q.top();
        q.pop();
        int u = t.to;
        if(vis[u])
            continue;
        vis[u] = 1;
        int sz = G[u].size();
        for (int i = 0; i < sz; i++) {
            int v = G[u][i].to;
            long long d = G[u][i].v;
            if(dis[u]+d<dis[v]) {
                dis[v] = dis[u] + d;
                q.push((node){v, dis[v]});
            }
        }
    }
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n;i++) {
        scanf("%1d", &a[i]);
    }
    for (int i = 1; i <= n;i++) {
        long long v = i;
        G[i].push_back((edge){i + 1, v});
        G[i].push_back((edge){i - 1, 0});
        if(a[i]==1) {
            int l = max(i - k, 1);
            int r = min(i + k, n) + 1;
            G[l].push_back((edge){r, v});
        }
    }
    G[n+1].push_back((edge){n, 0});
    dijkstra(1);
    printf("%lld\n", dis[n + 1]);
}

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 100;
 
long long dp[maxn];
int a[maxn];
 
 
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n;i++) {
        scanf("%1d", &a[i]);
    }
 
    deque<int> d;
    d.push_back(0);
 
    for (int i = 1; i <= n + k;i++) {
        dp[i] = dp[i - 1] + i;
        if(i-k>0&&a[i-k]==1) {
            while(!d.empty()&&d.front()<i-2*k-1)
                d.pop_front();
            dp[i] = min(dp[i], dp[d.front()] + i - k);
        }
        while(!d.empty()&&dp[d.back()]>=dp[i])
            d.pop_back();
        d.push_back(i);
    }
    long long ans = 1e18;
    for (int i = n; i <= n + k;i++) {
        ans = min(ans, dp[i]);
    }
    printf("%lld\n", ans);
}

[CF1324E] Sleeping Schedule

https://codeforces.com/contest/1324/problem/E

要么选 $a_i$ ,要么选 $a_i-1$

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2000 + 5;
int a[maxn];
int dp[maxn][maxn];
int main() {
    int n,h,l,r;
    cin >> n >> h >> l >> r;
    for (int i = 1; i <= n;i++) {
        scanf("%d", &a[i]);
    }
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= n;i++) {
        for (int j = 0; j < h;j++) {
            int x = (j + a[i] - 1) % h;
            int f = 0;
            if(l<=x&&x<=r)
                f = 1;
            dp[i][x] = max(dp[i-1][j] + f, dp[i][x]);
            x = (j + a[i]) % h;
            if(l<=x&&x<=r)
                f = 1;
            else
                f = 0;
            dp[i][x] = max(dp[i-1][j] + f, dp[i][x]);
        }
    }
    int ans = 0;
    for (int i = 0; i < h;i++) {
        ans = max(ans, dp[n][i]);
    }
    cout << ans << endl;
}

状压DP

找朋友

赵队出的题，找朋友

#include <bits/stdc++.h>
#include<stdint.h>
using namespace std;
#define int long long
#define scan(n) scanf("%lld", &(n))
#define scann(n, m) scanf("%lld%lld", &(n), &(m))
#define scannn(a, b, c) scanf("%lld%lld%lld", &(a), &(b), &(c))
#define prin(n) printf("%lld", (n))
#define pb push_back
#define mp make_pair
#define ms(a) memset(a, 0, sizeof(a))
#define fo(i, a, b) for (int i = (a); i <= (b); i++)
#define ro(i, a, b) for (int i = (a); i >= (b); i--)
#define dbg(args...) do {cout << #args << " : "<< args << endl;} 
const int inf = 0x3f3f3f3f;
const int maxn = (1<<21);
int x[25],y[25];
int n,f;
double dp[maxn];
bool check(int s,int t){
    for(int i=1;i<=n;i++){
        int x=(1<<i);
        if((!(s&x))&&(t&x))return false;
    }
    return true;
}
double dis(int i,int j){
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
double min_dis(int t,int j){
    vector<double>v;
    for(int i=1;i<=n;i++){
        int x=(1<<i);
        if(t&x){
            v.pb(dis(i,j));
        }
    }
    sort(v.begin(),v.end());
    if(v.size()<=1)return inf;
    return v[0]+v[1];
}
int32_t main() {
    int T;scan(T);
    while(T--){
        scan(n);
        int s=0;
        int xx=((1<<(n+1))-1)^1;
        for(int i=0;i<=maxn-1;i++)dp[i]=inf;
        fo(i,1,n){
            scannn(x[i],y[i],f);
            if(f)s^=(1<<i);
        }
        dp[s]=0;
        for(int i=s;i<=xx;i++){
            if(!check(i,s))continue;
            fo(j,1,n){
                int t=(1<<j);
                if((i&t)&&(!(s&t))){
                    int x=i^t;
                    dp[i]=min(dp[x]+min_dis(x,j),dp[i]);
                }
                else continue;
            }
        }
        if(dp[xx]==inf){
            cout<<"No Solution\n";
            continue;
        }
        printf("%.6lf\n",dp[xx]);
    }
    return 0;
}

区间DP

###[CF1199F] Rectangle Painting

https://codeforces.com/contest/1199/problem/F

给定一个 $n \times n$ 的矩阵,由 $"\#”,"."$ 组成，每次可以将 $h\times w$ 矩形内的 $"\#"$ 变成 $"."$

花费为 $max(h,w)$ ,求将所有 $"\#"$ 变成 $"."$ 的最小花费

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
char a[55][55];
int f[55][55][55][55];
int dp(int x,int y,int xx,int yy){
    if(f[x][y][xx][yy]!=-1)return f[x][y][xx][yy];
    int ans=max(xx-x+1,yy-y+1);
    fo(i,x,xx-1)ans=min(ans,dp(x,y,i,yy)+dp(i+1,y,xx,yy));
    fo(i,y,yy-1)ans=min(ans,dp(x,y,xx,i)+dp(x,i+1,xx,yy));
    return f[x][y][xx][yy]=ans;
}
int main(){
    int n;scanf("%lld",&n);
    fo(i,1,n)scanf("%s",a[i]+1);
    memset(f,-1,sizeof(f));
    fo(x,1,n){
        fo(y,1,n){
            fo(xx,1,n){
                fo(yy,1,n){
                    if(x>xx||y>yy)f[x][y][xx][yy]=0;
                    if(x==xx&&y==yy)f[x][y][xx][yy]=(a[x][y]=='#'?1:0);
                }
            }
        }
    }
    cout<<dp(1,1,n,n)<<endl;
    
}