题意：给定一个数组，求严格递增子序列的个数
思路：根据经典的LIS问题，很快就可以设计出状态转移方程， dp[i] = sum( dp[j] ) + 1, (0
题目链接：http://acm.fzu.edu.cn/problem.php?pid=2236
【DP|fzu oj 2236 第十四个目标 树状数组好题 dp】
#include
#include
#include using namespace std;
const int maxn = 100005;
const int mod = 1000000007;
int n, cnt;
int a[maxn], b[maxn], c[maxn], dp[maxn];
int bin_search(int num)
{
int l = 0, r = cnt - 1, m;
while(l <= r)
{
m = (l+r) >> 1;
if(b[m] > num) r = m - 1;
else if(b[m] < num) l = m + 1;
else return m;
}
return -1;
}int lowbit(int t)
{
return t & (-t);
}int getsum(int x)
{
int ans = 0;
while(x > 0)
{
ans = (ans + c[x]) % mod;
x -= lowbit(x);
}
return ans;
}void update(int x, int val)
{
while(x <= cnt)
{
c[x] = (c[x] + val) % mod;
x += lowbit(x);
}
}int main()
{
while(~scanf("%d", &n))
{
for(int i = 0;
i < n;
i++)
{
scanf("%d", &a[i]);
b[i] = a[i];
}
cnt = 1;
sort(b, b+n);
for(int i = 1;
i < n;
i++)
if(b[i] != b[i-1])
b[cnt++] = b[i];
memset(c, 0, sizeof(c));
memset(dp, 0, sizeof(dp));
int ans = 0;
for(int i = 0;
i < n;
i++)
{
int pos = bin_search(a[i]);
dp[i] = (getsum(pos) + 1) % mod;
//因为树状数组从1开始，所以这里的pos相当于pos-1
ans = (ans + dp[i]) % mod;
update(pos + 1, dp[i]);
}
printf("%d\n", ans);
}
return 0;
}
推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶（线性表）