预设性DP
从最简单的起
DP搬运工2
Description
给你 n,K ，求有多少个 1 到 n 的排列，恰好有 K 个数 i(1<i<n) 满足 ai−1,ai+1 都小于 ai 。
Input Format
一行两个整数 n,K 。
Output Format
一行一个整数 ans 表示答案 mod 998244353 。
Sample
样例输入1
4 1
样例输出1
16
样例输入2
10 3
样例输出2
1841152
Hint
对于 25% 的测试点， 1≤n,K≤10 ；
对于 50% 的测试点， 1≤n,K≤100 ；
对于 100% 的测试点， 1≤n,K≤2000 ；
保证数据有梯度
考虑\(dp_{i,j}\)表示一个长为\(i\)的序列,有\(j\)个数满足，注意一个数满足\(a_i>a_{i+1},a_{i-1}\)
我们考虑按顺序加入第\(i\)次插入\(i\)，考虑不增加的情况就是在满足的旁边插入，新插入一个一定满足条件,但与他相邻原来的就不满足了，增加一个又减少一个，因为有两个相邻的所以满足的就只有\(j\)个
考虑增加一个的,就是在剩下的情况中
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
#define pii pair<int,int>
#define ull unsigned long long
#define pb push_back
#define ts cout<<"----------------"<<endl;
#define bs bitset<65>
using namespace std;
const int N = 2005,mod=998244353;
int n,k;ll dp[N][N];
int main()
{
speed();
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
cin>>n>>k;
dp[1][0]=1;
dp[2][0]=2;
for(int i=3;i<=n;i++)
{
for(int j=0;j<=min(i/2,k);j++)
{
if(!dp[i-1][j])continue;
dp[i][j]=(dp[i][j]+dp[i-1][j]*(1ll*(j+1)<<1ll))%mod;
dp[i][j+1]=(dp[i][j+1]+dp[i-1][j]*(i-((j+1)<<1ll))%mod)%mod;
}
}
cout<<dp[n][k]<<endl;
return 0;
}
袋鼠
题目描述
有一个园子，里面有 n 个草丛排成一排，标号 1∼n，有一个袋鼠，从 s 出发，每次跳一步跳到一个其他的草丛，经过每个草丛恰好一次，最终到达 t。显然他会跳跃 n−1次为了不被人类发现，袋鼠每次跳跃的方向必须与前一次不同。
具体地，如果他现在在 now，他是从 prev 跳跃一次到达 now 的，然后他跳跃一次到达 next：
-
那么如果 prev<now，就必须有 next<now；
-
如果 now<prev，就必须有 now<next。
问从 s 到 t 的方案数模 109+7的结果。
两个路线不同，当且仅当草丛被访问的顺序不同。
保证至少有一种方案初始时可以往任意方向跳。
输入格式
一行三个整数 n,s,t。
输出格式
一行一个整数，代表答案。
样例 #1
样例输入 #1
4 2 3
样例输出 #1
2
数据范围与提示
对于 36% 的数据，2≤n≤100
对于 69% 的数据，2≤n≤1000
对于 100% 的数据，2≤n≤2×103，1≤s,t≤n
Bonus： 如果你已经 AK ，考虑 n≤106 怎么做
这道题，预设性DP，不知道欧拉路能不能做，反正不会，考虑\(dp_{i,j}\),表示长度为\(i\)的多个连续段总长度,有\(j\)个不相连的连续段符合条件
还是分析:
第一种把两个连续段连起来,\(dp_{i,j}=dp_{i-1,j+1}\times j\)有\(j+1-1\)个空;
第二种，新开一个连续段（目前只有一个数）\(dp_{i,j}=dp_{i-1,j-1}\times (j-(i>t)-(i>s))\)为什么要考虑\(i\)与\(t,s\)的大小，因为\(s,t\)必须分别接在首尾，所以\(i>s,t\)时,当前有\(j\)个连续段要除去头尾\(s,t\)
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
#define pii pair<int,int>
#define ull unsigned long long
#define pb push_back
#define ts cout<<"----------------"<<endl;
#define bs bitset<65>
using namespace std;
const int N = 2e3+5,mod=1e9+7;
int n,s,t;
ll dp[N][N];
int main()
{
speed();
freopen("kang.in","r",stdin);
freopen("kang.out","w",stdout);
cin>>n>>s>>t;//0 left
dp[1][1]=1;
for(int i=2;i<=n;i++)
{
for(ll j=1;j<=n;j++)
{
// if(i==1&&)
if(i!=s&&i!=t)dp[i][j]=(dp[i][j]+dp[i-1][j+1]*j%mod+dp[i-1][j-1]*(j-(i>s)-(i>t))%mod)%mod;
else dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
}
}
cout<<dp[n][1]<<endl;
return 0;
}
DP搬运工1
Description
给你 n,K ，求有多少个 1 到 n 的排列，满足相邻两个数的 max 的和不超过 K 。
Input Format
一行两个整数 n,K 。
Output Format
一行一个整数 ans 表示答案 mod 998244353 。
Sample
样例输入1
4 10
样例输出1
16
样例输入2
10 66
样例输出2
1983744
Hint
有 50 个 测试点，第 i 个测试点为 n=i ， K≤n2 。
设\(dp_{i,j,k}\)表示填到第\(i\)个数,有\(j\)个空位,和为\(k\),注意这里的空位是两个连续段相连,如\(1 3 5\)有\(2\)个空位
分两种大情况
第一种有\(0\)个空位，首尾考虑一下即可
第二种有多个空位(不考虑两端，因为无空位)
- 考虑放两个数中间，使两个连续段连在一块
- 考虑新开一个连续段
- 放在一个连续段的旁边
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
#define pii pair<int,int>
#define ull unsigned long long
#define pb push_back
#define ts cout<<"----------------"<<endl;
#define bs bitset<65>
using namespace std;
const int N = 55+5,mod=998244353;
int n,K;
ll dp[N][N][N*50];
int main()
{
speed();
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
cin>>n>>K;
dp[1][0][0]=1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=n-i+1;j++)
{
for(int k=0;k<=K;k++)
{
if(!dp[i-1][j][k])continue;
dp[i][j+1][k]=(dp[i][j+1][k]+dp[i-1][j][k]*2%mod)%mod;
dp[i][j][k+i]=(dp[i][j][k+i]+dp[i-1][j][k]*2%mod)%mod;
if(j)
{
dp[i][j][k+i]=(dp[i][j][k+i]+dp[i-1][j][k]*j*2%mod)%mod;
dp[i][j+1][k]=(dp[i][j+1][k]+dp[i-1][j][k]*j%mod)%mod;
dp[i][j-1][k+2*i]=(dp[i][j-1][k+2*i]+dp[i-1][j][k]*j%mod)%mod;
}
}
}
}
ll ans=0;
for(int i=0;i<=K;i++)ans=(ans+dp[n][0][i])%mod;
cout<<ans<<endl;
return 0;
}