上社网站建设,襄阳企业网站建设,wordpress手机版注册,服装网站建设环境分析正题
金牌导航 数据结构优化DP-1 题目大意
平面上有n个点#xff0c;让你选择若干点#xff0c;连接x坐标相邻的点#xff0c;其中连续上升或下降的为一段#xff0c;问你有多少中选择方案#xff0c;使得段数为k 解题思路
设fi,j,0/1f_{i,j,0/1}fi,j,0/1为到第i个点…正题
金牌导航 数据结构优化DP-1 题目大意
平面上有n个点让你选择若干点连接x坐标相邻的点其中连续上升或下降的为一段问你有多少中选择方案使得段数为k 解题思路
设fi,j,0/1f_{i,j,0/1}fi,j,0/1为到第i个点已经有j段且第j段下降/上升的方案数
那么分类讨论
1.先上升后下降 2.连续下降 3.先下降后上升 4.连续上升
对于找满足的转移点可以建树状数组解决 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100010
#define wyc 100007
using namespace std;
int n, m, x, a[N], g[N];
struct Tree
{int num, c[N];void add(int x, int y){num (num y) % wyc;for (; x 100000; x x-x)c[x] (c[x] y) % wyc;return;}int ask(int x){int sum 0;for (; x; x - x-x)sum (c[x] sum) % wyc;return sum; }int askk(int x){return (num wyc - ask(x)) % wyc;}
}T[11][2];
bool cmp(int x, int y)
{return g[x] g[y];
}
int main()
{scanf(%d%d, n, m);for (int i 1; i n; i){scanf(%d%d, x, a[i]);g[a[i]] x;}sort(a 1, a 1 n, cmp);for (int i 1; i n; i){T[0][0].add(a[i], 1);//没有连边的点T[0][1].add(a[i], 1);for (int j 1; j m; j){T[j][1].add(a[i], (T[j][1].ask(a[i] - 1) T[j - 1][0].ask(a[i] - 1)) % wyc);//先上升和先下降T[j][0].add(a[i], (T[j][0].askk(a[i]) T[j - 1][1].askk(a[i])) % wyc);}}printf(%d, (T[m][0].ask(100000) T[m][1].ask(100000)) % wyc);return 0;
}
