P2072 宗教问题

P2072 宗教问题

题目描述

已知一个地方有M种宗教(编号为1—M)，有N个教徒(编号为1—N)，每个教徒信且只信一种宗教。现在要按顺序把这N个教徒分成一些集体，每个集体的危险值定义为这个集体中的宗教种数，且一个集体的宗教种类不能超过K种，否则就会无限危险，

问： 1.这N个教徒至少要分为几个集体，

2.这些集体的危险值总和至少为多少。

题目分析

可以用动态规划的思想进行解题，而本题由两问，可以设定两个集合分别求解。

设f1[i]为前i个教徒分的集体数量。而对于含i边界的段可设为[j, i](1 <= j <= 1)

• 在第 i个教徒处进行分的话，此时上一段的末尾边界应为j-1,则 f1[i] = f1[j - 1] + 1
• 在第i个位置处不分段的话，则仍然为 f[i]
• 在两种情况中取最小值

设f2[i]为前i个教徒分的危险值。而对于含i边界的段可设为[j, i](1 <= j <= 1)，此段的宗教种类数为cnt.

• 在第 i个教徒处进行分的话，此时上一段的末尾边界应为j-1,则 f2[i] = f2[j - 1] + cnt
• 在第i个位置处不分段的话，则仍然为 f2[i]
• 在两种情况中取最小值
• 注：此时j要从大到小枚举，才可以得到相应区间的正确种类数

通过此两个状态转移方程，得到的f1[n]、f2[n]即为所需答案

code

#include

using namespace std;

const int N = 100010, INF = 1e9;
typedef long long ll;

int n, m, k, t;
int f1[N], f2[N], a[N];
bool st[N];

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 0; i <= n + 1; i ++) 
        f1[i] = 1e9, f2[i] = 1e9;

    f1[1] = 1, f2[1] = 1;
    for(int i = 2; i <= n; i ++)
    {
        memset(st, false, sizeof st);
        int cnt = 0;
        for(int j = i; j >= 1; j --)
        {
            if(!st[a[j]])
            {
                st[a[j]] = true;
                cnt ++;
            }
            if(cnt > k) break;
            f1[i] = min(f1[i], f1[j - 1] + 1);
            f2[i] = min(f2[i], f2[j -1] + cnt);           
        }
    }
    //for(int i = 1; i <= n; i ++) cout << f1[i] << "--" << f2[i] << "\n";

    cout << f1[n] << "\n" << f2[n];

    return 0;
}