[POI2013]BAJ-Bytecomputer

摘要

题意:一个序列只有 ,每次可以选一个 使 ,求操作最少次数使得整个序列非严格单调递增.

小清新的 DP 题~

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+6;
int n,a[N];
int f[N][3];//f[i,0/1/2] 表示把前 i 个数变单调且最后一个数的状态为 -1/0/1 的最少次数

int main(){scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    memset(f,0x3f,sizeof(f));
    f[1][a[1]+1]=0;
    for(int i=2;i<=n;i++){if(a[i]==1){f[i][0]=f[i-1][0]+2;// 拉 2 次
            f[i][1]=f[i-1][0]+1;// 拉 1 次
            f[i][2]=min(f[i-1][0],min(f[i-1][1],f[i-1][2]));
        }
        else if(a[i]==0){f[i][0]=f[i-1][0]+1;// 拉 1 次
            f[i][1]=min(f[i-1][0],f[i-1][1]);
            f[i][2]=f[i-1][2]+1;
        }
        else {f[i][0]=f[i-1][0];
            f[i][2]=f[i-1][2]+2;// 拉 2 次
        }
    }
    int ans=min(f[n][0],min(f[n][1],f[n][2]));
    if(ans>=0x3f3f3f3f)puts("BRAK");
    else printf("%d",ans);
    return 0;
}

 上一篇
高斯消元 高斯消元
摘要 Gaussian Elimination,一种求解线性方程组的算法 概述高斯消元是一种求解线性方程组的方法。 线性方程组与増广矩阵我们把 \left\{\begin{matrix} a_{1,1}x_1+a_{1,2}x_2+\c
2019.04.04
下一篇 
[POI2010]PIL-Pilots [POI2010]PIL-Pilots
摘要 近期以 POI 的题为主,因为小清新~ 题意:给定 n,k 和一个长度为 n 的序列,求最长的最大值最小值相差不超过 k 的子串 最大最小就是单调队列啦,又因为是找连续子串的最大长度,显然就是尺取法的思路,每次纳入一个新的元素时更新
2019.04.02
  目录