题解：CF1221D Make The Fence Great Again

· · 题解

一道小贪心、大诈骗的 DP 题。

贪心

发现一个栅栏的长度最多只会增长 2。因为一个栅栏最多只会受到两边栅栏的两种长度影响，如果增长多了，则一定存在一个其他栅栏长度不变，但当前栅栏长度更短的合法方案。

DP

定义状态 d_{i,j}，表示前 i 个点，第 i 个栅栏长度增长 j （j=0/1/2）的最少花费。

状态转移：

d_{i,j}=\sum_{j'=0}^{2}d_{i-1,j'}+b_i\times j \text{（}a_i+j\ne a_{i-1}+j'\text{）}

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
long long q,n,a[maxn],b[maxn],d[maxn][3];
void dp(int x,int y,int z)
{
    if(a[x-1]+y!=a[x]+z)
    d[x][z]=min(d[x][z],d[x-1][y]+b[x]*z);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    a[0]=-1e9;
    cin>>q;
    while(q--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
        for(int i=1;i<=n;i++)
        {
            d[i][0]=1e18;
            d[i][1]=1e18;
            d[i][2]=1e18;
            for(int k=0;k<3;k++)
            for(int kk=0;kk<3;kk++)
            dp(i,k,kk);
        }
        cout<<min({d[n][0],d[n][1],d[n][2]})<<"\n";
    }
}