NOIP2011提高组(选择客栈)
2024-09-28 12:59:52
题目链接: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;
}
最新文章
- UITextView添加一个placeholder功能
- Android问题-XE5提示";[DCC Fatal Error] Project1.dpr(1): F1027 Unit not found: &#39;System.pas&#39; or binary equivalents (.dcu/.o)";
- Jersey(1.19.1) - Client API, Using filters
- 基于局部敏感哈希的协同过滤算法之simHash算法
- 【iOS 7】使用UIScreenEdgePanGestureRecognizer实现swipe to pop效果
- nodejs概论
- centos安装Chromium
- Android 解决Gallery下ScrollView滑动事件冲突
- Oralce生成前N年的年数据
- iscsi 挂载网络存储及存储访问
- C语言的三目运算符
- VirtualBox安装Ubuntu16.04过程
- 剑指offer(1)
- Java NIO学习笔记---I/O与NIO概述
- POJ 2299 Ultra-QuickSort 离散化加树状数组求逆序对
- 一、初始PS软件
- Linux下开发python django程序(Cookie读写)
- Java 运用流传输文件
- windows下codeblocks报错undefined reference to `WSAStartup@8&#39;|
- 【POJ 2409】 Let it Bead(置换、burnside引理)
热门文章
- Memory Barriers
- 时间见证着—eternal life
- 在Ubuntu 12.04上配置iSCSI Target服务
- .Net之路(十五)图解LoadRunner压力測试
- 使用Eclipse Memory Analyzer分析内存
- css样式布局中position的那些事儿
- Hibernate单向“一对一”关联
- MongoDB密码设置(基于windows)
- js基础 js自执行函数、调用递归函数、圆括号运算符、函数声明的提升 js 布尔值 ASP.NET MVC中设置跨域
- 查看、修改linux系统的最大链接数限制、文件描述符限制、端口范围限制、虚拟内存等