考虑两个字符串右对齐的最佳解法。例如，有一个右对齐方案中字符串是AADDEFGGHC和ADCDEGH。

AAD_DEFGGHC
ADCDE__GH_

每一个数值匹配的位置值2分，一段连续的空格值-1分。所以总分是匹配点的2倍减去连续空格的段数，在上述给定的例子中，6个位置（A，D，D，E，G，H）匹配，三段空格，所以得分2*6+(-1)*3=9，注意，我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符，则既不得分也不失分。

请你写个程序找出最佳右对齐方案。

【输入文件】

输入文件包含两行，每行一个字符串，最长50个字符。字符全部是大字字母。

【输出文件】

一行，为最佳对齐的得分。

 【输入输出样例】

输入：
AADDEFGGHC
ADCDEGH

输出：
9

【参考程序】：

基本算法：
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
复杂度是O(V*Σn[i])。

转化为01背包问题
另一种好想好写的基本方法是转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度仍然是O(V*Σn[i])。

但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。

方法：
将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。
分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..n[i]两段来分别讨论得出(并不难，希望你自己思考尝试一下)

这样就将第i种物品分成了O(log n[i])种物品，将原问题转化为了复杂度为<math>O(V*Σlog n[i])的01背包问题，是很大的改进。

下面给出O(log amount)时间处理一件多重背包中物品的过程，其中amount表示物品的数量：

普通的优化：
做法：
     对于每件物品的数量，在每次循环是我们加个判断：对于当前的for的这个物品，它最终有没有改变到哪个背包，假如它每一个背包都没有改变到，那么当前物品后面的数量也是不会改变任何的背包（他们都是一样的嘛！），所有此时我们便可跳出当前物品的循环了.（时间挺理想的，对于一般的数据是很快的）
【参考程序】：

注意没有两个新兵的身高相同。

军官想找出哪一排士兵跳的总次数最多，好惩罚他们到厨房去工作。你的目标就是帮助军官找到这一排。

Input

输入的第一行包含了两个数N和K（2≤N≤10000，1≤K≤20）。接下来的K行每行包含N个整数。新兵已经按照身高编好了号（1号最高，N号最矮）。每一行是相应的一排，例如某一行的第一个整数代表这行的第一个人等等。

Output

输出跳跃次数最多的那一行的编号。如果有几行次数相同，则输出行编号最小的那个。

Sample Input

3 3
1 2 3
2 1 3
3 2 1

Sample Output
3

天文学家时常调查星图，星图在一个平面上表示出所有星星，而且每个星星都有笛卡尔坐标。星星的级别是不在它上面且不在它右面的星星的总数。 天文学家想知道每个星星的级别。
 

For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
举例来说,看上面的图。 5号星星的级别是3(由 1,2 和 4 号而得)。2 点和 4 号星星的级别是 1. 在这个图里只有一个级别为 0 的星星,两个级别为 1 的星星，一个级别为 2 的星星和一个级别为 3 的星星

You are to write a program that will count the amounts of the stars of each level on a given map.
你的任务是计算每个级别的星星总数

Input

The first line of the input contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.
第一行包含一个数 N (1<=N<=15000)。一下 N 行描述相应的星星(每行两个用空格隔开的整数 X 和 Y, 0<=X,Y<=32000)。平面上每个坐标最多只有一个星星。星星按 Y 的升序排列，Y 相等则按 X 的升序排列

5
1 1
5 1
7 1
3 3
5 5

1
2
1
1
0

分析：
   此题我用的是《树状数组》，对于每个点我们先按照x升序，x同就y升序，这样我们就保
证了每个后来的点肯定是在前面点的右边，就不会影响我们后面对于每个点的计算，再有对于
每个点我们也压迫计算我它的上司（即它影响的星星），这样我们的方法就出来了：
   每个点我们要做的第一步：先看它的下边有多少颗星星（不包括自己）代码：getsum(y+1)
因为我们开始从最左下的那个点开始，出来则可以判断当前星星它是属于那个级别的，那么我们
统计级别（level）那个单元即可++，再用自己的值去改变它的上司，因为虽然它不算入自己
但是对于所有它上司都将因为它增加一级，所以它要统计于它的上司范围里，代码：modify(y)
这样我们就可以统计每个星星的级别了。注意：0是十分危险的，因为lowbit(0)会死循环所以
我每个纵(y)坐标都向上升了一个格这样再上面的还是再上面，不会影响结果。

   算法优越性：(1):免去了每次的向左统计，每个来的都自动统计比本身低的星星算出自己级
别，最后自己y坐标++，那么后面的只需向下看即可.(省时间)
(2):对于每个左边排序后保证了每个后来的点是不会出现再前面的前面的，保证的算法的正确性

【参考程序】：//树状数组

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node
{
    long x,y;
} point[15002];
long c[32002],level[32002];
long n;
long lowbit(long x)
{
    return x^(x&(x-1));
}
void modify(long x)
{
    while (x<=32001)
    {
        c[x]++;
        x+=lowbit(x);
    }
}
long getsum(long x)
{
    long s=0;
    while (x)
    {
        s+=c[x];
        x-=lowbit(x);
    }
    return s;
}
int cmp(const void * s,const void * t)
{
    node i=*(node *)s,j=*(node *)t;
    if (i.x!=j.x) return i.x-j.x;
    else return i.y-j.y;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
      scanf("%d%d",&point[i].x,&point[i].y);
    qsort(point+1,n,sizeof(node),cmp);
    memset(c,0,sizeof(c));
    memset(level,0,sizeof(level));
    long k;
    for (int i=1;i<=n;i++)
    {
        k=getsum(point[i].y+1);//防止0的坏情况
        level[k]++;
        modify(point[i].y+1);
    }
    for (int i=0;i<=n-1;i++)
      printf("%d\n",level[i]);
    return 0;
}

input：
初始时，火车上没有学生；当同学们开始上火车时，年级主任从第一节车厢出发走到最后一节车厢，每节车厢随时都有可能有同学上下。年级主任走到第m节车厢时，他想知道第１到m这m节车厢上一共有多少学生，但是他没有调头往回走的习惯．也就是说每次当他提问时，m总会比前一次大

output：
有多少个A就输出多少个数，回答年级主任提出的问题。输出不要换行!

input：
10 7
A 1
B 1 1
B 3 1
B 4 1
A 2
A 3
A 10

output：
0
1
2
3

分析：
      来一个人就把所有的上司（我影响的火车）都加上这个数，下车的就是单纯的减去即可，有A 的就统计

【参考程序】：//树状数组