CF888D Almost Identity Permutations 题解
CF链接:Almost Identity Permutations
Luogu链接:Almost Identity Permutations
\( {\scr \color {Cyan}{\text{Solution}}} \)
前言
这好像是一道能用数学秒掉的题目
但由于我喜欢DP过菜,我们用DP来解决这个问题
分析
\( dp[i][j] \) 表示在 \( i \) 个数里有 \( j \) 个数位置满足 \( a[i]==i \)
答案很简单,就是\(\sum_{i=n-k}^{n} dp[n][i]\)
接下来考虑状态如何转移
\( dp[i][j] \) 可以由 \( dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1] \) 转移而来
- 从 \( dp[i−1][j−1] \) 转移,我们可以直接把新增的数放到增加的位置上去就可以了;
- 从 \( dp[i−1][j] \) 转移,新增的数不能放到自己的位置上,且必须要和\( i-1-j \)个其他的数字交换位置;
- 从 \( dp[i-1][j+1] \)转移,那么新增的数字和原先在自己位置上的数字(j+1种)可以进行交换(因为现在多了一个,所以要减少一个);
边界也要稍稍注意一下
\( j=0 \)时,并没有\( dp[i-1][j-1]\)
同理,\( i=j \)时,直接为\( 1 \)
诶,做完了
Code:
//From:201929
#include<bits/stdc++.h>
#define L long long
using namespace std;
L dp[1005][1005];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
dp[4][4]=1,dp[4][3]=0,dp[4][2]=6,dp[4][1]=8,dp[4][0]=9;
for(int i=5;i<=n;i++)
for(int j=0;j<=i;j++)
if(j==0) dp[i][j]=(i-1)*dp[i-1][j]+dp[i-1][1];
else if(j==i) dp[i][j]=1;
else dp[i][j]=dp[i-1][j-1]+(i-1-j)*dp[i-1][j]+(j+1)*dp[i-1][j+1];
L ans=0;
for(int i=n-k;i<=n;i++) ans+=dp[n][i];
printf("%lld",ans);
return 0;
}
/you-xi-kai-fa-fu-wu/cf888d-almost-identity-permutations-ti-jie-4389.html