Game HDU - 6669(2019百度之星-初赛一B题，思维+DP)

Game HDU - 6669(思维+DP)

题目链接：HDU - 6669

思路：

​ 对于区间 $[a,b]$[a,b]，关键点有 $a,a+1,b-1,b$a,a+1,b−1,b。我们首先处理出所有区间的关键点，然后去重。容易知道，对于每个任务完成的位置一定在某个区间的关键点上。

​ 那么我们用 $dp\left[i\right]\left[k\right]$dp[i][k]​代表站在关键点 $k$k​完成第 $i$i​个任务的最小步数。然后进行状态转移

​ 对于第 $i$i​个任务在关键点 $k$k​的最小步数，即 $dp\left[i\right]\left[k\right]$dp[i][k]​的转移如下。假设第 $i$i​个任务的完成区间为 $\left[a\right[i],b[i\left]\right]$[a[i],b[i]]​， $pos\left[k\right]$pos[k]​代表第 $k$k​个关键点的位置.

• $if：pos\left[k\right]\&lt;a\left[i\right]orpos\left[k\right]\&gt;b\left[i\right]$if：pos[k]<a[i] or pos[k]>b[i]​， $dp\left[i\right]\left[k\right]=inf$dp[i][k]=inf​
• $elseif：pos\left[k\right]\ge a[i-1]andpos\left[k\right]\le b[i-1]$else if：pos[k]≥a[i−1] and pos[k]≤b[i−1]， $dp\left[i\right]\left[k\right]=dp[i-1]\left[k\right]$dp[i][k]=dp[i−1][k]
• $else:dp\left[i\right]\left[k\right]$else:dp[i][k]一定由第 $i-1$i−1个任务区间的关键点转移过来的，那么枚举第 $i-1$i−1个区间的关键点转移到 $pos\left[k\right]$pos[k]的最小步数即可。

代码：

#include<bits/stdc++.h>
using  namespace  std;
typedef long long ll;
const int maxn=1e6+10;
const int inf=0x3f3f3f3f;
//对于区间[ai,bi]，关键点为ai,ai+1,bi-1,bi
/* 1.计算每个区间的关键点 2.顺着dp一下即可 */
const int N=1e3+10;
int dp[N][4000+2],a[N],b[N];
vector<int> keyps;
int getstep(int a,int b)
{
    if(a==b) return 0;
    return (abs(a-b)+1)/2;
}
int getpos(int a,int b,int k)
{
    switch(k)
    {
    case 0:
        return a;
    case 1:
        return (a+1>b)?-1:(a+1);
    case 2:
        return (b-1<a)?-1:(b-1);
    case 3:
        return b;
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n,ans=inf;
        keyps.clear();
        cin>>n;
        for(int i=1; i<=n; ++i)
        {
            cin>>a[i]>>b[i];
            keyps.push_back(a[i]);
            keyps.push_back(b[i]);
            if(a[i]+1<=b[i])
                keyps.push_back(a[i]+1);
            if(b[i]-1>=a[i])
                keyps.push_back(b[i]-1);
        }
        sort(keyps.begin(),keyps.end());
        keyps.erase(unique(keyps.begin(),keyps.end()),keyps.end());
        for(int k=0;k<keyps.size();++k){
            if(keyps[k]>=a[1]&&keyps[k]<=b[1]) dp[1][k]=0;
            else dp[1][k]=inf;
        }
        for(int i=2;i<=n;++i)
        {
            for(int k=0;k<keyps.size();++k){
                dp[i][k]=inf;
                 if(keyps[k]<a[i]||keyps[k]>b[i]) continue;
                 if(keyps[k]>=a[i-1]&&keyps[k]<=b[i-1]) dp[i][k]=min(dp[i][k],dp[i-1][k]);
                 else{
                    //枚举上个位置的四个关键点
                    for(int j=0;j<4;++j){
                        int ps=getpos(a[i-1],b[i-1],j);
                        if(ps==-1) continue;
                        int th=lower_bound(keyps.begin(),keyps.end(),ps)-keyps.begin();
                        dp[i][k]=min(dp[i][k],dp[i-1][th]+getstep(keyps[k],ps));
                    }
                 }

            }
        }
        for(int k=0;k<keyps.size();++k)
            ans=min(ans,dp[n][k]);
        cout<<ans<<endl;
    }
    return 0;
}