NOIP2011提高组（选择客栈）

题目大意：中文题。。。就不解释了

题目思路：看了其他巨巨的blog写的，dp思路

#include <iostream>                          ///时间复杂度O(n) 空间复杂度O(5n)

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <stack>

#include <cctype>

#include <queue>

#include <string>

#include <vector>

#include <set>

#include <map>

#include <climits>

#define lson root<<1,l,mid

#define rson root<<1|1,mid+1,r

#define fi first

#define se second

#define ping(x,y) ((x-y)*(x-y))

#define mst(x,y) memset(x,y,sizeof(x))

using namespace std;

#define gamma 0.5772156649015328606065120 //欧拉常数

#define MOD 100000007

#define inf 0x3f3f3f3f

#define N 200010

#define maxn 10001000

typedef long long LL;

typedef pair<int,int> PII;

int f[N];  ///保存第从1~i-1个客栈消费小于p的最大的客栈编号

int color[N]; ///保存1~i-1个客栈和i个客栈颜色相同的客栈个数

int c2[N]; ///c2[i]=1~i-1号客栈中与第i号客栈色调相同,且到第i号旅馆路上存在最低消费不大于p的客栈的客栈数目

int r[N];  ///第1~i-1的客栈中色调与i客栈相同的最大的编号

int _max[N]; ///maxc[i]=之前所有客栈中，色调为i的最大编号

int main()

{

    int a,i,n,m,p,b;

    scanf("%d%d%d",&n,&m,&p);

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

    {

        scanf("%d%d",&a,&b);

        r[i]=_max[a];

        if(b<=p) f[i]=i;

        else f[i]=f[i-];

        if(f[i]<r[i])c2[i]=c2[r[i]];

        else c2[i]=color[a];

        _max[a]=i;

        ++color[a];

    }

    int ans=;

    for(i=; i<=n; ++i) ans+=c2[i];

    cout<<ans<<endl;

    return ;

}

原文地址：传送门

今天又重做了一遍，有了自己的思路，而且感觉比较清晰

#include <iostream>                               ///时间复杂度O(kn) 空间复杂度O(2n+2k)

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <stack>

#include <cctype>

#include <queue>

#include <string>

#include <vector>

#include <set>

#include <map>

#include <climits>

#define lson root<<1,l,mid

#define rson root<<1|1,mid+1,r

#define fi first

#define se second

#define ping(x,y) ((x-y)*(x-y))

#define mst(x,y) memset(x,y,sizeof(x))

#define mcp(x,y) memcpy(x,y,sizeof(y))

#define Min(x,y) (x<y?x:y)

#define Max(x,y) (x>y?x:y)

using namespace std;

#define gamma 0.5772156649015328606065120

#define MOD 100000007

#define inf 0x3f3f3f3f

#define N 200005

#define maxn 10001000

typedef long long LL;

typedef pair<int,int> PII;

int a[N],b[N];

int color[]; ///当遍历到当前第i个客栈时，保留离当前客栈最近的（不包括当前客栈）

                ///价格低于p的客栈前面的不同色调客栈的分别的和

int hotel[]; ///当遍历到第i个客栈时保留的是前面不同色调客栈的分别的和

int ans;

int main()

{

    int i,j,n,c,p,tc,tp;

    scanf("%d%d%d",&n,&c,&p);

    for(i=; i<=n; ++i) scanf("%d%d",&a[i],&b[i]);

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

        tc=a[i]; tp=b[i];

        if(tp<=p){

            for(j=; j<=c; ++j)

                color[j]=hotel[j];

        }

        ans+=color[tc];

        if(tp<=p)

            ++color[tc];

        ++hotel[tc];

    }

    printf("%d\n",ans);

    return ;

}

第三次解题，这次有较大优化且更易理解

#include <iostream>                            ///时间复杂度O(n) 空间复杂度O(3k)
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <climits>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define mcp(x,y) memcpy(x,y,sizeof(y))
#define Min(x,y) (x<y?x:y)
#define Max(x,y) (x>y?x:y)
using namespace std;
#define gamma 0.5772156649015328606065120
#define MOD 100000007
#define inf 0x3f3f3f3f
#define N 200005
#define maxn 10001000
typedef long long LL;
typedef pair<int,int> PII;

int f[51];                    ///保留1~i-1色调与i相同且到i途中有合适咖啡馆的旅店总数
int hotel[51];                ///保留1~i-1色调与i相同的旅店总数
int last[51];                 ///保留1~i-1色调与i相同的旅店最后出现的位置
int temp;                    ///temp是整个算法的精髓，temp保留的是符合条件的咖啡馆最后出现的位置

int main()
{
    int i,j,n,c,p,x,y,ans=0;
    scanf("%d%d%d",&n,&c,&p);
    for(i=1; i<=n; ++i){
        scanf("%d%d",&x,&y);
        if(y<=p) temp=i;
        if(temp>=last[x]) f[x]=hotel[x];
        ans+=f[x];
        ++hotel[x];
        last[x]=i;
    }
    printf("%d\n",ans);
    return 0;
}