题目链接：http://codevs.cn/problem/1135/
题目大意：中文题。。。就不解释了
题目思路：看了其他巨巨的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=1; i<=n; ++i) { scanf("%d%d",&a,&b); r[i]=_max[a]; if(b<=p) f[i]=i; else f[i]=f[i-1]; if(f[i]<r[i])c2[i]=c2[r[i]]; else c2[i]=color[a]; _max[a]=i; ++color[a]; } int ans=0; for(i=1; i<=n; ++i) ans+=c2[i]; cout<<ans<<endl; return 0; }
原文地址：传送门
今天又重做了一遍，有了自己的思路，而且感觉比较清晰
#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[100]; ///当遍历到当前第i个客栈时，保留离当前客栈最近的（不包括当前客栈） ///价格低于p的客栈前面的不同色调客栈的分别的和 int hotel[100]; ///当遍历到第i个客栈时保留的是前面不同色调客栈的分别的和 int ans; int main() { int i,j,n,c,p,tc,tp; scanf("%d%d%d",&n,&c,&p); for(i=1; i<=n; ++i) scanf("%d%d",&a[i],&b[i]); for(i=1; i<=n; ++i){ tc=a[i]; tp=b[i]; if(tp<=p){ for(j=0; j<=c; ++j) color[j]=hotel[j]; } ans+=color[tc]; if(tp<=p) ++color[tc]; ++hotel[tc]; } printf("%d ",ans); return 0; }
第三次解题，这次有较大优化且更易理解
#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 ",ans);
return 0;
}