首页 > 其他 > 详细

HDU 5273 Dylans loves sequence(区间DP)

时间:2015-06-21 02:06:42      阅读:188      评论:0      收藏:0      [点我收藏+]

Dylans loves sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 114    Accepted Submission(s): 59


Problem Description
Dylans is given N技术分享 numbers a[1]....a[N]技术分享

And there are Q技术分享 questions.

Each question is like this (L,R)技术分享

his goal is to find the “inversions” from number L技术分享 to number R技术分享.

more formally,his needs to find the numbers of pair(x,y技术分享),
that Lx,yR技术分享 and x<y技术分享 and a[x]>a[y]技术分享
 

Input
In the first line there is two numbers N技术分享 and Q技术分享.

Then in the second line there are N技术分享 numbers:a[1]..a[N]技术分享

In the next Q技术分享 lines,there are two numbers L,R技术分享 in each line.

N1000,Q100000,LR,1a[i]2技术分享31技术分享?1技术分享
 

Output
For each query,print the numbers of "inversions”
 

Sample Input
3 2 3 2 1 1 2 1 3
 

Sample Output
1 3
Hint
You shouldn‘t print any space in each end of the line in the hack data.
 

Source
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
const int N = 1005;
#define LL __int64

int n,q,a[N],l,r,dp[N][N];
int main()
{
    while(scanf("%d%d",&n,&q)>0){
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        for(int k=1; k<n; k++)
        for(int i=1; i+k<=n; i++){
            int j=i+k;
            dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1];
            if(a[i]>a[j])
                dp[i][j]++;
        }
        while(q--){
            scanf("%d%d",&l,&r);
            printf("%d\n",dp[l][r]);
        }
    }
    return 0;
}


HDU 5273 Dylans loves sequence(区间DP)

原文:http://blog.csdn.net/u010372095/article/details/46575777

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!