(luogu1311)选择客栈

发表于 | 分类于 ，

思路:

用一个二维数组存储下每个位置之前的所有的颜色的客栈个数(即前缀和), 并记录下每一个在限制范围内的客栈

以这些客栈为分割点, 将整个区间分为若干段(不包括分割点)

对于每个分割点, 统计它之前的区间与后面的一段的方案数, 对分割点单独统计, 这样便可以做到不重复也不遗漏统计

以下图作为例子(第二行为编号,第三行为颜色,第四行为费用):
luogu1311_sample
其中, 2,5,7为限制范围内的客栈, 将客栈分为1~1,3~4,6~6,8~8四段

对第一个分割点2, 讨论1~4. 若不选2, 有1种方案; 若选2, 有1种方案

对第二个分割点5, 讨论1~6. 若不选5, 有2种方案; 若选5, 有3种方案

对第三个分割点7, 讨论1~8. 若不选7, 有4种方案; 若选7, 有2种方案

所以答案为13

下面是代码

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int Mn(200050);
int hn[Mn][55]; //即前面所讲的前缀和
vector<int> pp; //记录分割点位置
vector<int> pc; //记录分割点颜色
int main()
{
    int n,k,p;
    scanf("%d%d%d",&n,&k,&p);
    for(int i(1);i<=n;++i)
    {
        int clr,cst;
        scanf("%d%d",&clr,&cst);    //颜色和费用
        if(cst<=p)  { pp.push_back(i); pc.push_back(clr); }
        memcpy(hn[i],hn[i-1],sizeof hn[i]);
        ++hn[i][clr];   //更新前缀和
    }
    int ans(0); //答案
    for(int i(0);i<pp.size()-1;++i)
    {
        for(int j(0);j<k;++j)
            ans += hn[pp[i]-1][j] * (hn[pp[i+1]-1][j]-hn[pp[i]][j]);    //不考虑分割点的情况
        ans += hn[pp[i+1]-1][pc[i]]-1;  //考虑分割点的情况
    }
    for(int j(0);j<k;++j)   //对最后一个分割点特殊判断
        ans += hn[pp[pp.size()-1]-1][j] * (hn[n][j] - hn[pp[pp.size()-1]][j]);
    ans += hn[n][pc[pc.size()-1]]-1;
    cout << ans;
    return 0;
}