【dp+桶】Sorting Railway Cars CodeForces

【dp+桶】Sorting Railway Cars CodeForces - 606C

Bertha 。 2022-06-08 09:17 188阅读 0赞

Think:
1知识点：dp+桶
2反思：
（1）：认真读题，理解题意，补题过程中发现题目的一些关键点之前自己做的时候都没有发现，比如按照递增顺序和1<=Pi<=n这两个关键条件
（2）：不要固话思维，要经常反思和思考如何将知识点巧妙地结合在一起，将一些好的思想互相融合，进而尝试去创造新的算法
3方法：
最终状态为递增顺序，题目提示数据1<=Pi<=n，因此最终状态为按照1递增的等差数列，每次移动只能移动到首位或者末位，因此可思考是否为寻找最长的按照1递增的等差子序列，当找到最长的按照1递增的等差子序列，那么剩下的过程便是将其它元素按照一定顺序插入到首位或者末位，进而将问题锁定到如何寻找序列中的按照1递增的最长的等差子序列，进而思考是否含有动态转移方程，发现dp[num] = dp[num-1] + 1，之后思考如何通过num-1联系num，数据范围1<=N<=100000，思考桶的思想，发现可以通过下标联系关系，思考细节，代码实现
4思考：
（1）：dp的一些题目或许可以离散化之后通过下标联系转移关系

以下为Accepted代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int book[101400];
int main(){
    int n, i, x, ans;
    while(~scanf("%d", &n)){
        ans = 0;
        memset(book, 0, sizeof(book));
        for(i = 1; i <= n; i++){
            scanf("%d", &x);
            book[x] = book[x-1] + 1;
            ans = max(ans, book[x]);
        }
        printf("%d\n", n-ans);
    }
    return 0;
}