洛谷 题解 P2072 【宗教问题】

我看到大佬的题解，为什么第\(1\)个子任务也用\(DP\)算呢？完全可以用贪心啊。。。

言归正传。

对于第一个子任务，直接贪心，能取多少取多少，取满后清零再取。

对于第二个子任务，考虑\(DP\)。

设\(f_i\)表示前\(i\)个教徒的最少危险值，则有：

\(f_i=\min\{f_j+danger_{i,j}\}\) \((danger_{i,j}<=k)\)

其中\(danger_{i,j}\)表示\(i,j\)之间的危险值。

问题来了：\(danger_{i,j}\)怎么求呢？

\(1.\)在跑方程的时候暴力求解。

时间复杂度：\(O(n^3)\)，显然会\(T\)。

\(2.\)预处理。

令\(cnt\)为计数器，当发现新的宗教时\(cnt++\)，并且标记这个宗教，而每一段对应的\(danger_{i,j}\)即为\(cnt\)

时间复杂度：\(O(n^2)\)，可过。

至于边界，显然有\(f_0=0,f_1=1\)

目标自然是\(f_n\)

\(AC\) \(Code\) (代码中的\(sum_{i,j}\)即为\(danger_{i,j}\))

#include <iostream>
#include <cstring>
using namespace std;

int n, m, k, a[10010], cnt, ans, sum[1010][1010], f[1010];
bool vis[10010];

int main() {
    cin >> n >> m >> k;
    for (int i=1; i<=n; i++) 
        cin >> a[i];
    for (int i=1; i<=n; i++) {
        cnt = 0;
        memset(vis, false, sizeof(vis));// 一定要清空!
        for (int j=i; j<=n; j++) {
            if (!vis[a[j]]) {
                vis[a[j]] = true;
                cnt++;
            }
            sum[i][j] = cnt;
        }
    }
    cnt = 0;
    memset(vis, false, sizeof(vis));//注意，出来时也要清空！我被坑了好长时间TAT
    for (int i=1; i<=n; i++) {
        if (!vis[a[i]]) {
            vis[a[i]] = true;
            cnt++;
        }
        if (cnt > k) {
            ans++;
            cnt = 1;
            memset(vis, false, sizeof(vis));//记得清空！
            vis[a[i]] = true;
        }
        if (i == n)
            ans++;
    }
    cout << ans << endl;
    f[0] = 0;
    f[1] = 1;//初始化莫忘掉
    for (int i=2; i<=n; i++) {
        f[i] = 1e9;//因为取最小值，所以初值要赋大
        for (int j=1; j<=i; j++) 
            if (sum[j][i] <= k) //而且危险值不能超过k
                f[i] = min(f[i], f[j-1]+sum[j][i]);
    }
    cout << f[n] << endl;
    return 0; //完结撒花！
}

洛谷 题解 P2072 【宗教问题】

原文：https://www.cnblogs.com/zyh-cr7/p/12237196.html