近期DP题目
几道DP题目
牛客练习赛139C，25武汉邀请赛FG等
题意：
给定一个 \(n\times m\) 的网格图，我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格。左上角为 $(1,1)$ ，右下角为 $(n,m)$ ，每个格子包含一个整数价值，使用 $a_{i,j}$ 表示。 一个光标在上面移动，从 $(s,1)$ 出发，每次可以向右或者向下移动，每个格子至多经过一次。当光标移动到 $(n,i) \left(1\le i\le m \right)$ 格子，也就是最后一行的某个格子时，继续向下移动则会到达 $(1,i)$ 格子。大卫需要移动光标到达 $(t,m)$ ，求最终大卫能获取的最大价值和。
题解：
二维DP+限制。定义状态 $dp[i][j]$ 表示在 $(i,j)$ 位置时的最大价值和。
因为纵向是可以走到底然后从上面走下来的，所以我们考虑转移的时候从左往右一列一列的转移。
设 \(s_n=\sum_{i=1}^n a[i][j]\)，则转移方程为 \(dp_{i,j} \leftarrow \max_{k} \left( dp_{k,j-1} + \begin{cases} s_i - s_{k-1} & \text{if } ~k < i \\ s_n - (s_{k-1} - s_i) & \text{if } ~k > i \end{cases} \right)\) 观察上面式子，如果在 \(k>i\) 的情况下，
因为这里面只有 $s_{k-1}$ 是不固定的，我们找到最小的 $k$ 进行转移就行了;两种对于从下转移和从上转移不同情况，对应 \(l\) 数组和 \(r\) 数组，分别使用DP求出对于 \(i\) 的最大值。
DP数组可以滚动。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e3+10,M=1e6+10,inf=1e18+10;
ll Tt=1,n,m,s,t;
ll dp[2][N],a[N][N],l[N],r[N],sum[N];
void solve(){
cin>>n>>m>>s>>t;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
for(int i=1;i<=n;i++) dp[0][i]=-inf;
dp[0][s]=0;
for(int j=1;j<=m;j++){
int now=j&1,pre=(j-1)&1;
for(int i=0;i<=n+1;i++){
l[i]=r[i]=-inf,sum[i]=0;
dp[now][i]=dp[pre][i],dp[now][i]=0;
}
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i][j];
for(int i=1;i<=n;i++) l[i]=max(l[i-1],dp[pre][i]-sum[i-1]);
for(int i=n;i>=1;i--) r[i]=max(r[i+1],dp[pre][i]+sum[n]-sum[i-1]);
for(int i=1;i<=n;i++) dp[now][i]=max(l[i],r[i+1])+sum[i];
}
cout<<dp[m&1][t]<<"\n";
}
int main(){
while(Tt--) solve();
return 0;
}
题意：
有一张 \(n\) 个点 \(m\) 条边的简单无向带权连通图 \(G\)。可以进行 \(n\) 次操作，每次操作如下：
选择一个仍未被删除的点 \(u\)，然后删除点 \(u\) 和当前与 \(u\) 相连的所有边（即其中一个端点是 \(u\) 的边）。假设本次删除的边的边权分别是 \(w_1, w_2,\dots w_k\)，则本次操作的代价是 \(k\times (w_1+w_2+\dots+w_k)\) 。
你的总代价是这 \(n\) 次操作的代价和。将图中所有点和边都删除（即把图删空）的最小总代价是多少。
题解：
状压DP。定义状态为 \(f[s]\) 为已经删过点的集合为 \(s\) 时所能取得的最小代价，那么容易得出状态转移方程
\(f_S = \min_{\substack{1 \leq j \leq n \& j \notin S}} \left\{ f_{S \cup j} + \sum_{l \notin S} [(l,j)\in E] \sum_{l \notin S \& (l,j) \in E}{w_{l,j}} \right\}\) 边界条件是当 \(S={1,2,...,n}\) 时，\(f_S=0\) ，因为删完了就不需要再付出代价了。答案即为 \(f_\empty\)，因为最开始的时候一个点也没删。
时间复杂度为 \(O(2^nn^2)\)，可以通过 \(n ≤ 16\) 的范围。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e18;
ll n,m,g[10][10],dp[1<<10];
bool vis[1<<10];
ll f(ll x){
if(vis[x]) return dp[x];//记忆化搜索
if(x==(1<<n)-1) return 0;//全未删
ll ans=1e18;
for(int j=1;j<=n;j++){
if(!(x&(1<<(j-1)))){//第j个点已经删除了
ll k=0,v=0;
for(int l=1;l<=n;l++){//枚举所有与j点相连的边
if(!(x&(1<<(l-1)))&&g[j][l]>0){//第l个点也删了,且j和l有边
k++,v+=g[j][l];//删的边数++，值+
}
}
ans=min(ans,f(x|(1<<(j-1)))+k*v);
}
}
vis[x]=1,dp[x]=ans;
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;cin>>u>>v>>w;
g[u][v]=g[v][u]=w;
}
cout<<f(0);
return 0;
}
题意：
给定两个字符串 \(s,t\)，扶苏想让你求出一个字符串 \(x\)，满足：
- \(x\) 是 \(s\) 的子串。
- \(x\) 是 \(t\) 的子序列。
- 在所有满足前述两条的字符串中，$x$ 的长度最长。
- 在所有满足前述三条的字符串中，$x$ 的字典序最小。
请你帮她求出这样的字符串 $x$。
题解：
此题我使用枚举子串+DP判断子序列超时，时间复杂度太大。
可以 \(O(n^2)\) 枚举子串。写出 \(O(nlog m)\) 的判断子序列。
考虑优化，注意到判断子序列其实是可以继承于上一段的结果，于是我们少一个判断子序列花费的 n，此时复杂度来到 \(O(Tn^2logm)\) 。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
string s,t;cin>>s>>t;
int n=s.size(),m=t.size();
s=" "+s,t=" "+t;
vector<int> ve[35];
for(int i=1;i<=m;i++) ve[t[i]-'a'].push_back(i);
string ans;
for(int i=1;i<=n&&n-i+1>=ans.size();i++){
string flc;
for(int j=i,x=-1;j<=n;j++){
auto tmp=upper_bound(ve[s[j]-'a'].begin(),ve[s[j]-'a'].end(),x);
if(tmp==ve[s[j]-'a'].end()) break;
x=ve[s[j]-'a'][tmp-ve[s[j]-'a'].begin()];
flc+=s[j];
}
if(flc.size()>ans.size()||flc.size()==ans.size()&&flc<ans) ans=flc;
}
cout<<ans<<'\n';
}
int main(){
int T;cin>>T;
while(T--) solve();
return 0;
}
题意：
有 $n$ 组物品 ，第 $i$ 组物品有 $a_i$ 个，每个物品的重量为 $2^{b^i}$。
有 $m$ 个背包，每个背包的承重为 $k$。求最小的 $k$，使得所有 $\sum_{i=1}^n a_i$ 个物品都能被放入背包中，每个背包物品总重量不超过 $k$。同一组不同物品可放不同背包。
题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=6e6+10,INF=4e18,p=998244353;
ll n,m;
vector<pair<ll,ll> > v(N);
ll fpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=(res*a)%p;
a=(a*a)%p;
b>>=1;
}
return res;
}
void solve(){
map<ll,ll> mp;
cin>>n>>m;
for(int i=1;i<=n;i++){
ll a,b;cin>>a>>b;
mp[b]+=a;
}
ll idx=0;
for(auto i:mp){
if(i.second>m){
ll sub=i.second-m;
mp[i.first]-=sub;
if(sub&1) sub++,mp[i.first]--;
mp[i.first+1]+=sub/2;
}
if(mp[i.first]) v[++idx]={i.first,mp[i.first]};
}
ll pre=-1,res=0,fu=0;
for(ll i=idx;i>=1;i--){
if(pre==-1){
res+=fpow(2,v[i].first);
fu=m-v[i].second;
}else{
if(fu&&pre-v[i].first>40){
cout<<res<<"\n";
return ;
}else{
if(fu){
for(ll j=pre;j>v[i].first;j--){//2^j
fu*=2;
if(fu>2*m){cout<<res<<"\n";return;}
}
}
if(fu>=v[i].second) fu-=v[i].second;
else{
v[i].second-=fu;
res=res+fpow(2,v[i].first);
res%=p;
fu=m-v[i].second;
}
}
}
pre=v[i].first;
}
cout<<res<<"\n";
}
int main(){
int T;cin>>T;
while(T--) solve();
return 0;
}
题意：
有一个 $n\times m$ 的网格，每个格子写一个整数，第 $i$ 行第 $j$ 列的格子里写着整数 $a_{i,j}$。
从 $(1,1)$ 走到 $(n,m)$ ，只能往下走或者往右走。
一条路径的价值定义为路径上不同整数的数量。对于所有可能路径，求价值之和。
题解：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
const int mod = 998244353;
const int N = 1e6 + 10;
ll fact[N], infact[N];
int n, m;
ll qmi(ll a, ll b){
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void init(){
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++) fact[i] = fact[i - 1] * i % mod;
infact[N - 1] = qmi(fact[N - 1], mod - 2);
for (int i = N - 2; i; i --) infact[i] = infact[i + 1] * (i + 1) % mod;
}
ll C(int a, int b){
if (b < 0 || a - b < 0) return 0;
return fact[a] * infact[b] % mod * infact[a - b] % mod;
}
bool cmp(PII a, PII b){
if (a.first == b.first) return a.second < b.second;
return a.first < b.first;
}
ll func1(vector<PII>& a, int len){
vector<ll> f(len, 0);
ll res = 0;
for (int i = 0; i < len; i ++) {
f[i] = C(a[i].first + a[i].second - 2, a[i].first - 1);
for (int j = 0; j < i; j ++) {
if (a[j].first <= a[i].first && a[j].second <= a[i].second) {
f[i] = (f[i] - f[j] * C(a[i].first - a[j].first + a[i].second - a[j].second, a[i].first - a[j].first) % mod + mod) % mod;
}
}
ll num = f[i] * C(n - a[i].first + m - a[i].second, n - a[i].first) % mod;
res = (res + num) % mod;
}
return res;
}
ll func2(vector<vector<ll>>& g, ll tol, int c){
vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, 0));
dp[1][1] = 1;
ll res = 0;
if (g[1][1] == c) dp[1][1] = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++) {
if (i == 1 && j == 1) continue;
if (g[i][j] == c) continue;
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
}
res = (tol - dp[n][m] + mod) % mod;
return res;
}
void solve(){
cin >> n >> m;
vector<vector<ll>> g(n + 1, vector<ll>(m + 1));
set<int> v;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++) {
cin >> g[i][j];
v.insert(g[i][j]);
}
map<int, vector<PII>> c;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
c[g[i][j]].emplace_back(i, j);
for (auto it : v) sort(c[it].begin(), c[it].end(), cmp);
int mid = sqrt(n * m);
ll tol = C(n + m - 2, n - 1);
ll ans = 0;
for (int it : v) {
auto a = c[it];
int len = a.size();
ll x;
if (len <= mid) x = func1(a, len);
else x = func2(g, tol, it);
ans = (ans + x) % mod;
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
init();
int t;cin >> t;
while (t --) solve();
return 0;
}
