题解 P2528 【[SHOI2001]排序工作量之新任务】
QQQfy
·
·
题解
简单的DP+毒瘤的简单的贪心
0. 闲聊
秒出方程，然后输出方案懵比了。。。以为是一般套路在dp里记录方案。。。然而居然是个贪心（逃
1.dp状态
#### 2.转移方程
$dp[i][j]=\sum_{k<=j}{dp[i-1][j-k]}
很好理解啊
这里要注意k的取值范围是0至i-1,然后再判断j>=k
因为只确定了前i-1个的总数，加上一个新数最多使逆序对数增多i-1个。
3.边界
第一问答案就在$dp[n][t]$中
#### 4.贪心
从后往前列举，找第一个比当前数小的数，交换，这样可以使得每次交换只增多一个逆序对，由于是从后往前列举，就使得字典序最小了
~~我在口胡些什么~~
大家结合代码手动~~膜~~模拟一遍就知道了
#### 5.喜闻乐见的代码
```cpp
#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