hdu 5273（递推）

57 阅读 0 评论 38 点赞

我是靠谱客的博主犹豫曲奇，最近开发中收集的这篇文章主要介绍hdu 5273（递推），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：给定多个询问，找到区间[l,r]的逆序数对数。

解题思路：

这道题目其实就是递推，只要找到递推公式即可。dp[i][j]表示在区间[i,j]内，逆序数的对数，则有递推式：dp[i][j] = dp[i][j-1] + num[i][j]，其中num[i][j]表示a[i]对区间[l,r]的贡献。剩下的问题是如何求num[i][j]，其实这里也是利用递推的，只不过要根据逆序数的定义，倒着推出num[i][j]，即num[i][j]，是靠num[i+1][j]推过来的。。。

AC:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 1001;
int dp[maxn][maxn],num[maxn][maxn]; //num[i][j]表示在区间[i,j]里，j贡献的逆序数
int a[maxn];

int main()
{
	int n,q;
	while(scanf("%d%d",&n,&q)!=EOF)
	{
		for(int i = 1; i <= n; i++)
			scanf("%d",&a[i]);
		memset(dp,0,sizeof(dp));
		memset(num,0,sizeof(num));
		//求num[i][j]
		for(int i = 1; i <= n; i++)
			for(int j = i-1; j > 0; j--)
			{
				if(a[j] > a[i]) num[j][i] = num[j+1][i]+1;
				else num[j][i] = num[j+1][i];
			}
		for(int i = 1; i <= n; i++)
			for(int j = i+1; j <= n; j++)
				dp[i][j] = dp[i][j-1] + num[i][j];
		int l,r;
		while(q--)
		{
			scanf("%d%d",&l,&r);
			printf("%dn",dp[l][r]);
		}
	}
	return 0;
}