自动搬运

查看原文

来自洛谷，原作者为

	QQQfy **

搬运于2025-08-24 21:38:42，当前版本为作者最后更新于2019-02-18 10:42:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单的DP+毒瘤的简单的贪心

0. 闲聊

秒出方程，然后输出方案懵比了。。。以为是一般套路在dp里记录方案。。。然而居然是个贪心（逃

1.dp状态

$dp[i][j]$表示前$i$个数，已经出现了$j$个逆序对

2.转移方程

$dp[i][j]=\sum_{k<=j}{dp[i-1][j-k]}$

很好理解啊

这里要注意$k$的取值范围是$0$至$i-1$,然后再判断$j>=k$

因为只确定了前$i-1$个的总数，加上一个新数最多使逆序对数增多$i-1$个。

3.边界

$dp[1][0]=1$,就是第一个数，没有逆序对（废话人家一个数当然是单身狗

第一问答案就在$dp[n][t]$中

4.贪心

从后往前列举，找第一个比当前数小的数，交换，这样可以使得每次交换只增多一个逆序对，由于是从后往前列举，就使得字典序最小了

我在口胡些什么

大家结合代码手动膜模拟一遍就知道了

5.喜闻乐见的代码

#include<bits/stdc++.h>
using namespace std;

long long a[30],dp[30][300],n,t;

int main()
{
	cin>>n>>t;
	for (int i=1;i<=n;i++) a[i]=i;
	if (t==0)
	{//特判
		cout<<1<<endl;
		for (int i=1;i<=n;i++) cout<<i<<" ";
		return 0;
	}
    //dp
	dp[1][0]=1;
	for (int i=2;i<=n;i++)
		for (int j=0;j<=i*(i-1)/2;j++)
			for (int k=0;k<i;k++)
				if (j>=k) dp[i][j]+=dp[i-1][j-k];
	cout<<dp[n][t]<<endl;
	//贪心
    for (int i=n-1;i>=1;i--)
		for (int j=n;j>i;j--)
		{
			t--;
			swap(a[i],a[j]);
			if (t==0) 
			{
				for (int k=1;k<=n;k++) cout<<a[k]<<" ";
				return 0;
			}
		}
	return 0;
}

6.我要赞qwq