动态规划学习笔记

连续段DP

P5599 [CEOI 2016] kangaroo

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define N 2005
using namespace std;
int dp[N][N];
signed main(){int n,s,t;scanf("%lld%lld%lld",&n,&s,&t);dp[1][1]=1;for(int i=2;i<=n;i++){for(int j=1;j<=n;j++){if(i==s||i==t)dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;else dp[i][j]=(dp[i-1][j-1]*(j-(int)(i>s)-(int)(i>t))+dp[i-1][j+1]*j)%mod;}}printf("%lld\n",dp[n][1]);return 0;
}

将问题转化为一个排列，然后从小往大插入数，状态为当前形成j个连续段的方案数，根据题目要求进行转移

四边形不等式优化

P10861 [HBCPC2024] MACARON Likes Happy Endings

对于solve函数维护一个求解区间和一个决策区间，对求解区间进行分治，然后遍历决策区间求出mid的决策点继续分治

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define N 2005
using namespace std;
int dp[N][N];
signed main(){int n,s,t;scanf("%lld%lld%lld",&n,&s,&t);dp[1][1]=1;for(int i=2;i<=n;i++){for(int j=1;j<=n;j++){if(i==s||i==t)dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;else dp[i][j]=(dp[i-1][j-1]*(j-(int)(i>s)-(int)(i>t))+dp[i-1][j+1]*j)%mod;}}printf("%lld\n",dp[n][1]);return 0;
}