P3558 [POI2013] BAJ-Bytecomputer 题解

DarliWang · 2024-03-26 21:09:46 · 题解

不以-1/0/1分类来转移的动态规划思路

状态设计

我们定义状态 f(i, -1/0/1)，表示第 i 个数变成 j 的最低代价。

状态转移

考虑当 i-1 位置为 k，i 位置为 ai，希望将其变为 j，关系如下：

i-1 ---- i

k --- (ai)->j

接下来我们想知道将 ai 变为 j 的代价。

当 j = ai 时，没有代价，同时k 的取值也无所谓。
当 j ≠ ai 时,使j满足j ≥ k才能合题意。设代价为 t，有 ai + t * k = j，且 t > 0，联立求出 t 为：

t = \frac{j - ai}{k} \quad \text{[(j-ai)与k同号]}

可得状态转移方程：

当 j ≠ ai 时：

f(i, j) = \min_{k ≤ j} \left\{ f(i-1, k) + \frac{j - ai}{k} \right\}

当 j = ai 时：

f(i, j) = \min_{k \in \{-1, 0, 1\}} \{ f(i-1, k) \}

代码（j偏移为j+1）

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int N=1e6+6;
int f[N][3];
int a[N];
int n,ans;
int main()
{
    int i,j,k;cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    memset(f,0x3f,sizeof(f));
    f[1][a[1]+1]=0;
    for(i=2;i<=n;i++){
        for(j=-1;j<=1;j++){
                if(j==a[i]){
                    for(k=-1;k<=j;k++) f[i][j+1]=min(f[i][j+1],f[i-1][k+1]);
                    continue;
                }
                for(k=-1;k<=j;k++)
                    if((j-a[i])*k>0)
                        f[i][j+1]=min(f[i][j+1],f[i-1][k+1]+(j-a[i])/k);
        }
    }
    ans=min({f[n][0],f[n][1],f[n][2]});
    if(ans==inf) cout<<"BRAK";
    else cout<<ans;

    return 0;
}