DP III

· · 个人记录

A

题目简介：有N个range和M个点问要最少几个range才能覆盖整个区域。

贪心？？？

排序这N个range，每一次看可以选的range中找左边能够被覆盖，右边最大的。

O(NlogN) 
const ll maxn=1e5+5;
//dp[j]+max(i+1,j)
pii arr[maxn];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m;
    cin>>n>>m;
    REP(i,n) cin>>arr[i].f>>arr[i].s;
    sort(arr,arr+n);
    int ans=1,pv=0;
    if(arr[0].f>1){
        cout<<-1;
        return 0;
    }
    REP1(i,n-1){
        if(arr[i].f<=arr[pv].s+1 and arr[i].s>arr[pv].s){
            int opt=i;
            while(i<n and arr[i].f<=arr[pv].s+1){
                if(arr[i].s>arr[opt].s) opt=i;
                ++i;
            }
            pv=opt;
            i=opt;
            ans++;
        }
    }
    if(arr[pv].s<m){
        cout<<-1;
        return 0;
    }
    cout<<ans;
}

B

题目简介：给序列长度N问有几个长度为M的IS（递增序列）

naive dp 就是dp 代表结尾是i长度为j的IS有几个。 转移为 dp[i][j]= \sum_{k<i} dp[k][j-1]

哇复杂度真美 O(10^9*M*10^9)

第一个优化显然是离散化这个序列。这样复杂度就缩小到 O(N^2M)

接下来可以发现转移可以用BIT来优化因为询问的区间是连续的。

最后复杂度就变成 O(NMlogN)

代码

#include<iostream>
#include<vector>
#include<map>
using namespace std;
//省略恶心模版
int arr[maxn];
struct BIT{
    int bit[maxn];
    int n;
    void resize(int _n){
        n=_n;
        REP(i,n+5) bit[i]=0;
    }
    void upd(int p,int x){
        ++p;
        while(p<=n){
            bit[p]+=x;
            if(bit[p]>=MOD) bit[p]-=MOD;
            p+=lowb(p);
        }
    }
    int query(int p){
        ++p;
        int ans=0;
        while(p){
            ans+=bit[p];
            if(ans>=MOD) ans-=MOD;
            p-=lowb(p);
        }
        return ans;
    }
}bit[maxn];
void solve(){
    int n,m;
    cin>>n>>m;
    map<int,int> mp;
    REP(i,n) cin>>arr[i],mp[arr[i]]=0;
    int cnt=0;
    for(auto &x:mp) x.s=cnt++;
    REP(i,n) arr[i]=mp[arr[i]];
    REP1(i,m) bit[i].resize(n);
    REP(j,n){
        bit[1].upd(arr[j],1);
        for(int i=2;i<=m;i++){
            bit[i].upd(arr[j],bit[i-1].query(arr[j]-1));
        }
    }

    cout<<bit[m].query(n-1)<<'\n';
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int t;
    cin>>t;
    REP1(i,t){
        cout<<"Case #"<<i<<": ";
        solve();
    }
}

D

题目简介：给N个人放到一些shifts使得每一个shift没有超过K个人。

枚举第i个shift放k个人。 $dp[i][j]=\sum_{k<=j}{dp[i-1][j-k]* {j \choose k}} 
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        BigInteger[][] dp =new BigInteger[55][55];
        BigInteger[][] c =new BigInteger[55][55];
        for(int i=0;i<55;i++) for(int j=0;j<55;j++) dp[i][j]=c[i][j]=BigInteger.ZERO;
        c[0][0]=BigInteger.ONE;
        for(int i=1;i<55;i++){
            c[i][0]=c[i][i]=BigInteger.ONE;
            for(int j=1;j<i;j++){
                c[i][j]=c[i-1][j-1].add(c[i-1][j]);
            }
        }
        Scanner s=new Scanner(System.in);
        dp[0][0]=BigInteger.ONE;
        BigInteger ans=BigInteger.ZERO;
        int n=s.nextInt(),k=s.nextInt();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int z=1;z<=Math.min(j,k);z++){
                    dp[i][j]=dp[i][j].add(dp[i-1][j-z].multiply(c[j][z]));
                }
            }
            ans=ans.add(dp[i][n]);
        }
        System.out.println(ans);
    }
}

G

题目简介：给N个任务可以把他们分成不同的subarray然后cost是 (prev time+S+T_x+T_{x+1} +....+ T_{x+k}) \cdot (F_x+F_{x+1}+..F_{x+k}) 问最少cost是多少。

第一个问题是怎样来维护目前时间是多少，因为如果放在dp试里面会导致复杂度爆炸。我们发现其实不需要记得花了多少因为我们可以直接把S加到所有后面的elements。所以我们就得到一个dp方程。

dp[i]=min(dp[k]+S \cdot (pref_f[n]-pref_f[k])+pref_t[i] \cdot (pref_f[i]-pref_f[k])

接下来我们发现这个dp可以斜率优化因为式子可以用一个来表示。

dp[i]=min(dp[k]+S \cdot pref_f[n]+ pref_t[i] \cdot pref_f[i] - S \cdot pref_f[k]- pref_t[i] \cdot pref_f[k])

斜率是-pref_f[k] 所以是递减的，询问点是 pref_t[i]，所以是递增的。

复杂度为 O(N)

#include<iostream>
#include<deque>
using namespace std;
//省略恶心模版
const ll maxn=1e4+5;
struct line{
    ll m,c;
    ll eval(ll x){
        return x*m+c;
    }
    ld intersect(line x){
        return (ld)(x.c-c)/(m-x.m);
    }
};
ll t[maxn],c[maxn];
ll dp[maxn];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,s;
    cin>>n>>s;
    REP1(i,n){
        cin>>t[i]>>c[i];
        t[i]+=t[i-1],c[i]+=c[i-1];
    }
    deque<line> dq;
    line z;
    z.m=0,z.c=0;
    dq.pb(z);
    REP1(i,n){
        while(sz(dq)>=2 and dq[0].eval(t[i]+s)>=dq[1].eval(t[i]+s)) dq.pop_front();
        dp[i]=dq[0].eval(t[i]+s)+s*(c[n])+t[i]*c[i];
        line x;
        x.m=-c[i],x.c=dp[i];
        while(sz(dq)>=2 and dq[sz(dq)-2].intersect(x)<=dq.back().intersect(dq[sz(dq)-2])) dq.pop_back();
        dq.pb(x);
    }
    cout<<dp[n];
}

H

题目简介：有N个猫和P个人，每个人可以沿着路上拿猫。每一个路都有一个距离d_i。猫会在 t_i 时间 h_i 出现。安排每一个人使得猫的等待时间最少。

dist[i]=dist[i-1]+d[i]

每一个猫如果人在t[i]-dist[h_i] 出现就不需要等待。

所以我们可以吧题目简化成给一个阵列，分成K段使得(最大值 * 长度每一段的和 )的和是最小的。

dp[i][j]=min(dp[k][j-1]+arr[i] \cdot (i-k) - pref[i]+pref[k])

接下来我们发现可以斜率优化因为可以表达成一条线。

dp[i][j]=min(dp[k][j-1]+dist[i] \cdot i- pref[i]- dist[i] \cdot k +pref[k])

斜率为-k，询问点为dist[i]

复杂度为 O(NP)

#include<bits/stdc++.h>
using namespace std;
//省略恶心模版
const ll maxn=1e5+5;
struct line{
    ll m,c;
    ll eval(ll x){
        return x*m+c;
    }
    ld intersect(line x){
        return (ld)(x.c-c)/(m-x.m);
    }
};
#define int ll
//dec slope inc point
ll dp[105][maxn];  
int arr[maxn];
ll pref[maxn];
//dp[i][j]=min(dp[i-1][k]+arr[j]*j-arr[j]*k-pref[j]+pref[k])
int32_t main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m,p;
    cin>>n>>m>>p;
    REP1(i,n-1){
        cin>>arr[i];
        arr[i]+=arr[i-1];
    }
    vector<int> v;
    REP(i,m){
        int a,b;
        cin>>a>>b;
        --a;
        v.pb(b-arr[a]);
    }
    sort(ALL(v));
    v.emplace(v.begin(),0);
    REP1(i,m) pref[i]=pref[i-1]+v[i];
    REP1(j,m) dp[0][j]=INF64;
    REP1(i,p){
        deque<line> dq;
        dq.pb({0,0});
        REP1(j,m){
            while(sz(dq)>=2 and dq[0].eval(v[j])>=dq[1].eval(v[j])) dq.pop_front();
            dp[i][j]=dq[0].eval(v[j])+v[j]*j-pref[j];
            line x={-j,dp[i-1][j]+pref[j]};
            while(sz(dq)>=2 and dq[sz(dq)-2].intersect(x)<=dq.back().intersect(dq[sz(dq)-2])) dq.pop_back();
            dq.pb(x);
        }
    }
    cout<<dp[p][m];
}