题目链接: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=; 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;
}

最新文章

  1. UITextView添加一个placeholder功能
  2. Android问题-XE5提示&quot;[DCC Fatal Error] Project1.dpr(1): F1027 Unit not found: &#39;System.pas&#39; or binary equivalents (.dcu/.o)&quot;
  3. Jersey(1.19.1) - Client API, Using filters
  4. 基于局部敏感哈希的协同过滤算法之simHash算法
  5. 【iOS 7】使用UIScreenEdgePanGestureRecognizer实现swipe to pop效果
  6. nodejs概论
  7. centos安装Chromium
  8. Android 解决Gallery下ScrollView滑动事件冲突
  9. Oralce生成前N年的年数据
  10. iscsi 挂载网络存储及存储访问
  11. C语言的三目运算符
  12. VirtualBox安装Ubuntu16.04过程
  13. 剑指offer(1)
  14. Java NIO学习笔记---I/O与NIO概述
  15. POJ 2299 Ultra-QuickSort 离散化加树状数组求逆序对
  16. 一、初始PS软件
  17. Linux下开发python django程序(Cookie读写)
  18. Java 运用流传输文件
  19. windows下codeblocks报错undefined reference to `WSAStartup@8&#39;|
  20. 【POJ 2409】 Let it Bead(置换、burnside引理)

热门文章

  1. Memory Barriers
  2. 时间见证着—eternal life
  3. 在Ubuntu 12.04上配置iSCSI Target服务
  4. .Net之路(十五)图解LoadRunner压力測试
  5. 使用Eclipse Memory Analyzer分析内存
  6. css样式布局中position的那些事儿
  7. Hibernate单向“一对一”关联
  8. MongoDB密码设置(基于windows)
  9. js基础 js自执行函数、调用递归函数、圆括号运算符、函数声明的提升 js 布尔值 ASP.NET MVC中设置跨域
  10. 查看、修改linux系统的最大链接数限制、文件描述符限制、端口范围限制、虚拟内存等