清橙 A1210. 光棱坦克
2024-09-04 18:10:09
A1210. 光棱坦克
时间限制:1.0s 内存限制:512.0MB
总提交次数: AC次数: 平均分:
试题来源
2010中国国家集训队命题答辩
问题描述
一个平面直角坐标系上,有N个点,标号为1到N,其中第i个点的坐标为(x[i], y[i])。
求满足以下两个条件的点列{p[i]}的数目(假设{p[i]}的长度为M):
1) 对任意1 <= i < j <= M,必有y[p[i]] > y[p[j]];
2) 对任意3 <= i <= M,必有x[p[i-1]] < x[p[i]] < x[p[i-2]]或者x[p[i-2]] < x[p[i]] < x[p[i-1]]。
求满足条件的非空序列{p[i]}的数目,结果对一个整数Q取模。
求满足以下两个条件的点列{p[i]}的数目(假设{p[i]}的长度为M):
1) 对任意1 <= i < j <= M,必有y[p[i]] > y[p[j]];
2) 对任意3 <= i <= M,必有x[p[i-1]] < x[p[i]] < x[p[i-2]]或者x[p[i-2]] < x[p[i]] < x[p[i-1]]。
求满足条件的非空序列{p[i]}的数目,结果对一个整数Q取模。
输入格式
第1行是两个由空格隔开的整数:N和Q。
第2行到第N+1行,每行有两个整数。其中的第i行的两个整数分别是x[i]和y[i]。
第2行到第N+1行,每行有两个整数。其中的第i行的两个整数分别是x[i]和y[i]。
输出格式
输出文件只有一行,包含一个整数,表示序列{p[i]}的数目对Q取模的结果。
样例输入
4 100
2 2
3 1
1 4
4 3
2 2
3 1
1 4
4 3
样例输出
14
样例说明
一共4个点,位置如下:
如果M=4, 那么只有1种序列符合要求,如下图所示:
如果M = 3,那么有3种序列符合要求,如下图:
如果M = 2,那么有6种序列符合要求,如下图:
如果M = 1,也就是点列只包含一个点的情况。那么有4种序列。明显都符合要求。
所以一共就有1 + 3 + 6 + 4一共14种序列符合要求。
数据规模和约定
对于25%的数据,N <= 50;对于40%的数据,N <= 700;对于60%的数据,N <= 2000;对于70%的数据,N <= 4000;对于100%的数据,1 <= N <= 7000。
对于100%的数据,有1 <= Q <= 1000000000。
对于50%的数据,保证对任何的i,x[i]和y[i]是1到N之间的整数;对于100%的数据,保证对任何的i,x[i]和y[i]都是1到2000000000之间的整数。
对于100%的数据,保证有当i != j时,有x[i] != x[j]且y[i] != y[j]。
对于100%的数据,有1 <= Q <= 1000000000。
对于50%的数据,保证对任何的i,x[i]和y[i]是1到N之间的整数;对于100%的数据,保证对任何的i,x[i]和y[i]都是1到2000000000之间的整数。
对于100%的数据,保证有当i != j时,有x[i] != x[j]且y[i] != y[j]。
/*
首先把点按照x坐标排序(不是y坐标)
设dp[i][j][0/1]代表只考虑前i个点,以第j个点为起点,下一个点在它的左边/右边的方案数.
当i增加1时,从右到左 对每个之前的点考虑第i个点造成的贡献.
当这个点在第i个点以上时,第i个点可以更新这个点的dp值;
当这个点在第i个点以下时,这个点可以更新第i个点的dp值.
显然是可以滚动数组的.
复杂度O(n*n)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
int x,y;
bool operator < (const node o)const{
return x<o.x;
}
}pot[];
int n,md,dp[][];
int main(){
scanf("%d%d",&n,&md);
for(int i=;i<=n;i++)scanf("%d%d",&pot[i].x,&pot[i].y);
sort(pot+,pot+n+);
for(int i=;i<=n;i++){
dp[i][]=dp[i][]=;
for(int j=i-;j>=;j--){
if(pot[j].y<pot[i].y){
dp[i][]+=dp[j][];
if(dp[i][]>=md)dp[i][]-=md;
}
else{
dp[j][]+=dp[i][];
if(dp[j][]>=md)dp[j][]-=md;
}
}
}
int ans=;
for(int i=;i<=n;i++){
ans+=dp[i][];
if(ans>=md)ans-=md;
ans+=dp[i][];
if(ans>=md)ans-=md;
}
ans-=n;
if(ans<)ans+=md;
printf("%d\n",ans);
return ;
}
最新文章
- 一步步学习javascript基础篇(0):开篇索引
- C语言编程实现Linux命令——who
- (转)apache和nginx的区别
- Fragment 和 FragmentActivity的使用
- REG_SZ和REG_EXPAND_SZ的区别
- POJ 1155 TELE 背包型树形DP 经典题
- YEBIS
- Java_swing控件实例
- 新闻头条应用源码ios版
- 教你用笔记本破解无线路由器password
- 7-1 DBA顾问培训内容@20141230
- Oracle (内连接)
- 2013第49周一jsp标签
- win32 Message(MSG)消息处理
- JavaScript发布/订阅实例
- 翻译 | Placing Search in Context The Concept Revisited
- windows快速搭建FTP工具Serv-U FTP Server
- 【不懂】spring bean生命周期
- LeetCode题解Maximum Binary Tree
- Eclipse修改编码方式
热门文章
- Queue 输出数据
- Linux配置redis服务器
- codeforces 707D D. Persistent Bookcase(dfs)
- 【leetcode刷题笔记】Integer to Roman
- 【二叉树的递归】03判断二叉树中有没有和为给定值的路径【Path Sum】
- Java集合操作类Collections的一些常用方法
- CH6802 車的放置 和 CH6B24 Place the Robots
- What is Photon Server?
- Poj 2017 Speed Limit(水题)
- JavaScript之JMap