光棱坦克
题目描述
Description
一个平面直角坐标系上，有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取模。
Input
第1行是两个由空格隔开的整数：N和Q。 第2行到第N+1行，每行有两个整数。其中的第i行的两个整数分别是x[i]和y[i]。
Output
输出文件只有一行，包含一个整数，表示序列{p[i]}的数目对Q取模的结果。
Sample Input
4 100
2 2
3 1
1 4
4 3
Sample Output
14
Hint
如果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]。
70%
设f[i][j]表示当前选的点为i，y坐标为j
显然可以按x从小到大排序+离散化y，转移可以递推，从f[i][j]推到f[i][y[i]]（j≠y[i]）
如果推到某个位置，且该位置的i’>i，那么可以转移到f[i’][j]
这样做时间是O(n2)，但是常数较大（n=7000时跑了3s）
100%
考虑一种比较玄♂学的dp
把点按x从小到大排序，设f[i]表示找到的序列右端点为i，下一个要往左找的方案数，g[i]反之
则对于每个i，从大到小枚举j，若y[j]<y[i]，则f[i]+=g[j]，否则g[j]+=f[i]
正确性可以画图，发现每次转移的实质是从y小的转移到大的，所以还是满足无后效性
注意当长度为1时被算了两次
时间还是O(n2)，但是常数很小
code
#include <algorithm>
#include <iOStream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%mod
using namespace std;
struct type{
int x,y;
} a[7001];
int f[7001];
int g[7001];
int b[7001];
int n,mod,i,j,k,l,ans;
bool cmp(type a,type b)
{
return a.x<b.x;
}
int main()
{
// freopen("tank14.in","r",stdin);
// freopen("S8_13_2.in","r",stdin);
scanf("%d%d",&n,&mod);
fo(i,1,n)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
fo(i,1,n)
{
f[i]=1;
fd(j,i-1,1)
if (a[i].y>a[j].y)
add(f[i],g[j]);
else
add(g[j],f[i]);
g[i]=1;
}
fo(i,1,n)
{
add(ans,f[i]);
add(ans,g[i]);
}
ans-=n;
if (ans<0)
ans+=mod;
printf("%d\n",ans);
}
文章最后发布于: 2019-08-13 21:30:40
相关阅读
现在物价飞涨，无论我们工作多么努力，每年的工资涨幅仍然比不过通货膨胀，在这种情况下，我们就要另外地想办法来增加家庭的收入，以此来提
投资理财的方法多种多样，对于我们大多数普通投资人来说细分选择适合自己的投资方式，可以少走很多弯路起到事半功倍的效果。小编这里
A5创业网（公众号：iadmin5）8月16日报道，《怪物猎人 世界》前几日因游戏内容未完全符合政策法规要求，被要求整改下架，WeGame平台的好评率
我们处在一个物价飞涨的年代，无论什么东西，车、房、衣、食等等一切的价格都随着日新月异的社会不断攀升。你说房子贵的买不起，我们可
天缘博客近期出现很多关于光盘压片、刻录的词汇，为了让大家大致了解一下一个软件企业尤其是对于微软这样视软件为生命的企业如何处