【题解】洛谷P1311 [NOIP2011TG] 选择客栈（递推）

题目来源：洛谷P1311

思路

纯暴力明显过不了这道题

所以我们要考虑如何优化到至多只能到nlogn

但是我们发现可以更优到O(n)

我们假设我们当前寻找的是第二个人住的客栈i

那么第一个人住的客栈肯定在i之前

如果在枚举的时候发现一家客栈满足小于可承受价格

那么这家客栈左边与i客栈颜色相同的都可以视为一种方案

所以我们需要一个数组sum[k]记录到i之前第k种颜色一共有几家客栈

last[k]数组存下第k种颜色在i之前的最后一家客栈（判断满足价格的客栈颜色是否在此这种颜色最后一家位置的后面）

num[k]数组存下第k种颜色到i之前一共有几种可行方案

枚举时每次记录下满足价格的客栈i

观察其位置是否满足大于跟它同色的客栈

如果满足的话num数组更新为sum的值

每次枚举都要更新ans加上当前客栈颜色可行的方案（因为前面的可行的话对此客栈同意可行）sum数组 last数组

代码

#include<iostream>

using namespace std;

#define maxn 55

int n,m,p,ans,col,cost,temp;

int sum[maxn],num[maxn],last[maxn];

int main()

{

    cin>>n>>m>>p;

    for(int i=;i<=n;i++)

    {

        cin>>col>>cost;

        if(cost<=p) temp=i;//记录满足价格的位置

        if(temp>=last[col]) num[col]=sum[col];//如果大于同色的最后一个客栈位置即可更新

        ans+=num[col];

        last[col]=i;

        sum[col]++;

    }

    cout<<ans;

}