HDU - 5542 The Battle of Chibi(LIS+树状数组优化)

The Battle of Chibi

Cao Cao made up a big army and was going to invade the whole South China. Yu Zhou was worried about it. He thought the only way to beat Cao Cao is to have a spy in Cao Cao‘s army. But all generals and soldiers of Cao Cao were loyal, it‘s impossible to convince any of them to betray Cao Cao.

So there is only one way left for Yu Zhou, send someone to fake surrender Cao Cao. Gai Huang was selected for this important mission. However, Cao Cao was not easy to believe others, so Gai Huang must leak some important information to Cao Cao before surrendering.

Yu Zhou discussed with Gai Huang and worked out NN information to be leaked, in happening order. Each of the information was estimated to has aiai value in Cao Cao‘s opinion.

Actually, if you leak information with strict increasing value could accelerate making Cao Cao believe you. So Gai Huang decided to leak exact MM information with strict increasing value in happening order. In other words, Gai Huang will not change the order of the NN information and just select MM of them. Find out how many ways Gai Huang could do this.

InputThe first line of the input gives the number of test cases, T(1≤100)T(1≤100). TT test cases follow.

Each test case begins with two numbers N(1≤N≤103)N(1≤N≤103) and M(1≤M≤N)M(1≤M≤N), indicating the number of information and number of information Gai Huang will select. Then NN numbers in a line, the ithith number ai(1≤ai≤109)ai(1≤ai≤109) indicates the value in Cao Cao‘s opinion of the ithith information in happening order.OutputFor each test case, output one line containing Case #x: y, where xx is the test case number (starting from 1) and yy is the ways Gai Huang can select the information.

The result is too large, and you need to output the result mod by 1000000007(109+7)1000000007(109+7).Sample Input

2
3 2
1 2 3
3 2
3 2 1

Sample Output

Case #1: 3
Case #2: 0

Hint

In the first cases, Gai Huang need to leak 2 information out of 3. He could leak any 2 information as all the information value are in increasing order.
In the second cases, Gai Huang has no choice as selecting any 2 information is not in increasing order.

题意:求一个序列中长度为m的最长上升子序列个数。

设dp[i][j]表示以当前位置i结束的长度为j的序列个数。

容易想到O(n^3)的做法。开始想用记忆化搜索将复杂度降低一些,再加上若干剪枝,仍然会T。

考虑到问题涉及小于(大于)某个数的数的和,因此应该想到用树状数组优化。

使用lower_bound将所有数离散化,还要注意在dp的同时更新树状数组,时间复杂度为O(n^2*logn)。

//注释部分为优化前

#include<bits/stdc++.h>
#define MAX 1005
#define MOD 1000000007
#define lowbit(x) x&(-x)
using namespace std;
typedef long long ll;

int a[MAX],b[MAX];
int n,m;
ll dp[MAX][MAX];

ll sum(int x,int y){
    ll ans=0;
    while(1<=x){
        ans+=dp[x][y];
        ans%=MOD;
        x-=lowbit(x);
    }
    return ans;
}
void add(int x,int y,int z){
    while(x<=n){
        dp[x][y]+=z;
        dp[x][y]%=MOD;
        x+=lowbit(x);
    }
}
int main()
{
    int tt=0,t,i,j,k;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        sort(b+1,b+n+1);
        for(i=1;i<=n;i++){
            a[i]=lower_bound(b+1,b+n+1,a[i])-b;
        }
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++){
            //dp[i][1]=1;
            add(a[i],1,1);
            for(j=2;j<=m;j++){
                //dp[i][j]=dp[i-1][j];
                //for(k=1;k<i;k++){
                //    if(a[k]<a[i]){
                //        dp[i][j]+=dp[k][j-1];
                //        dp[i][j]%=MOD;
                //    }
                //}
                ll temp=sum(a[i]-1,j-1);
                add(a[i],j,temp);
            }
        }
        //printf("Case #%d: %I64d\n",++tt,dp[n][m]);
        printf("Case #%d: %I64d\n",++tt,sum(n,m));
    }
    return 0;
}

原文地址:https://www.cnblogs.com/yzm10/p/9774771.html

时间: 10-11

HDU - 5542 The Battle of Chibi(LIS+树状数组优化)的相关文章

HDU 5542 The Battle of Chibi dp+树状数组

题目:http://acm.hdu.edu.cn/showproblem.php?pid=5542 题意:给你n个数,求其中上升子序列长度为m的个数 可以考虑用dp[i][j]表示以a[i]结尾的长度为j的上升子序列有多少 裸的dp是o(n2m) 所以需要优化 我们可以发现dp的第3维是找比它小的数,那么就可以用树状数组来找 这样就可以降低复杂度 #include<iostream> #include<cstdio> #include<cstring> #include

ccpc_南阳 C The Battle of chibi dp + 树状数组

题意:给你一个n个数的序列,要求从中找出含m个数的严格递增子序列,求能找出多少种不同的方案 dp[i][j]表示以第i个数结尾,形成的严格递增子序列长度为j的方案数 那么最终的答案应该就是sigma(dp[i][m]); 显然有:dp[i][j] = sigma(dp[k][j - 1]); 其中 1 <= k < i 且 a[k] < a[i]; 题目要求严格递增,这个限制怎么解决? hdu4719这道题同样是这样处理,即我们只需要从小到大dp就行了. 但是复杂度是O(n^3)的,显然

HDU 2227 Find the nondecreasing subsequences (DP+树状数组+离散化)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2227 Find the nondecreasing subsequences                                  Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)                                             

【转】关于LIS和一类可以用树状数组优化的DP 预备知识

原文链接 http://www.cnblogs.com/liu-runda/p/6193690.html 预备知识 DP(Dynamic Programming):一种以无后效性的状态转移为基础的算法,我们可以将其不严谨地先理解为递推.例如斐波那契数列的递推求法可以不严谨地认为是DP.当然DP的状态也可以是二维/三维的,某一维的含义也不仅仅是指某个数列的第几项. 树状数组(BIT or fenwick tree):一种高效地动态维护一个序列并动态求取前缀和的数据结构.修改某个元素/求一次前缀和的

[noip科普]关于LIS和一类可以用树状数组优化的DP

预备知识 DP(Dynamic Programming):一种以无后效性的状态转移为基础的算法,我们可以将其不严谨地先理解为递推.例如斐波那契数列的递推求法可以不严谨地认为是DP.当然DP的状态也可以是二维/三维的,某一维的含义也不仅仅是指某个数列的第几项. 树状数组(BIT or fenwick tree):一种高效地动态维护一个序列并动态求取前缀和的数据结构.修改某个元素/求一次前缀和的时间复杂度均为O(logn) 2 LIS 好了现在假设你们都会打树状数组了(如果不会的话,baidu一发吧

Hdu 5458 Stability (LCA + 并查集 + 树状数组 + 缩点)

题目链接: Hdu 5458 Stability 题目描述: 给出一个还有环和重边的图G,对图G有两种操作: 1 u v, 删除u与v之间的一天边 (保证这个边一定存在) 2 u v, 查询u到v的路径上有几条桥. 解题思路: 这个题目有很多次操作,包含查询和删边两类,首先想到的是连通分量加缩点.如果按照顺序来,删边时候求桥就是问题了.所以可以离线处理,然后一边记录答案一边加边缩点. 对于一个图,把连通分量缩成一个点后,这个图就成为了一棵树, 然后深度差就等于桥的数目.查询的时候对于(u, v)

UvaLive 6667 Longest Chain (分治求三元组LIS&amp;树状数组)

题目链接: here 题意: 和hdu4742类似.区别就是一部分三元组是直接给出的.还有一部分是用他给的那个函数生成的.还有就是这里的大于是严格的大于a>b必须ax>bx,ay>by,az>bz. 思路: 思路也和hdu4742here类似.只是有几个比较棘手的问题.现在变成严格大于了.对于y还是很好办的.我们在排序y的时候可以使的标号大的排在前面这样就可以防止y和它一样的更新它了.感觉比较麻烦的是x一样怎么办.这个真没想出什么好办法.就只有x和mid+1的x不一样的建一个树状数

hdu 5654 xiaoxin and his watermelon candy 树状数组维护区间唯一元组

题目链接 题意:序列长度为n(1<= n <= 200,000)的序列,有Q(<=200,000)次区间查询,问区间[l,r]中有多少个不同的连续递增的三元组. 思路:连续三元组->递推O(n)将第一次出现该三元组的下标记录到树状数组中,并且用一个Next[]来表示递推关系,即同一个三元组下一次出现的位置是Next[x];这很关键,在之后按照左边界处理时(有点像莫队算法),一直递推在l+1左侧重复出现的三元组,为了把该三元组推到出现在[l,r]或者[r+1,..]中,这样不重不漏.

HDU 4455 Substrings --递推+树状数组优化

题意: 给一串数字,给q个查询,每次查询长度为w的所有子串中不同的数字个数之和为多少. 解法:先预处理出D[i]为: 每个值的左边和它相等的值的位置和它的位置的距离,如果左边没有与他相同的,设为n+8(看做无穷). 考虑已知w=k的答案,推w = k+1时,这时每个区间都将增加一个数,即后n-k个数会增加到这些区间中,容易知道,如果区间内有该数,那么个数不会加1,,即D[i] > k时,结果++,即查询后n-k个数有多少个D[i] > k 的数即为要加上的数,然后最后面还会损失一个区间,损失的

HDU 4267 A Simple Problem with Integers (树状数组)

A Simple Problem with Integers Time Limit: 5000/1500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Description Let A1, A2, ... , AN be N elements. You need to deal with two kinds of operations. One type of operation is to add a given