个人做dp的目前感觉是分析问题是否由子问题构成，并假设状态然后多写出各个的状态之间的转换；
https://codeforces.com/gym/102001/problem/L
可以贪心也可以DP
dp[i][j]指的是前i个数字中删除j个数字的最大值(j < i)考虑第j个数字删不删除若删除则问题转化为前i-1个数字删除j-1个数字
若不删除则是前i-1个数字删除j个数字，状态转移方程为：
dp[i][j] = min(dp[i-1][j] * 2 + s[i] - '0',dp[i-1][j]);
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
typedef long double LD;
typedef long long ll;
const int N = 70;
ll dp[N][N],k;
char s[N];
int main() {
cin >> k;
scanf("%s",s+1);
memset(dp,0x3f,sizeof dp);
int len = strlen(s+1);
dp[1][0] = 1;
for(int i=2; i<=len; i++) {
dp[i][0] = dp[i-1][0] * 2 + s[i] - '0';
for(int j=1; j<i; j++) {
dp[i][j] = min(dp[i-1][j] * 2 + s[i] - '0',dp[i-1][j-1]);
}
}
for(int i=0; i<=len; i++) {
if(dp[len][i] <= k) {
printf("%d\n",i);
break;
}
}
return 0;
}
2022ICPC网路预选赛！
https://pintia.cn/problem-sets/1574060137151397888/problems/1574060247893606401
dp[i][j] = 指的是2 ~ i-1 中删除j个数字的最大ans；
考虑删除分为k种：
删除i之前连续的j个数字，j-1个数字,j-2个数字，0个数字！
那么状态转移有dp[i][j] =
以图片为例子:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
#define int ll
const int N = 1e3+9;
int a[N];
int val[N][N],dp[N][N];
inline void _main() {
int n;
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
for(int l = 1; l<n; l++) {
for(int r = l+1; r <= n; r++) {
val[l][r] = (a[r] - a[l]) * (a[r] - a[l]);
}
}
for(int i=1; i<=n; i++) {
ll temp = 0;
if(i == 1) temp = 0;
else {
for(int j=1; j<i; j++) temp += (a[j+1] - a[j]) * (a[j+1] - a[j]);
}
dp[i][0] = temp;
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n-2; j++) {
if(i - j >= 2) {
for(int k=0; k<=j; k++) {
dp[i][j] = max(dp[i][j],dp[i-k-1][j-k] + val[i-k-1][i]);
}
}
}
}
for(int i=1; i<=n; i++) {
if(i * 2 >= n - 2) cout<<dp[n][n-2]<<"\n";
else cout<<dp[n][2*i]<<"\n";
}
}
signed main() {
int _;
_ = 1;
while(_--)
_main();
return 0;
}
https://codeforces.com/gym/103389/problem/C
状压dp 爆搜dfs T 考虑将图形无用的边剪枝，由于求的是最大值a -> b -> c 肯定比 a -> c 更优！
用邻接矩阵存图并类似于Floyd删除无用的边！
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 40,M = N * N / 2;
int c[N],w[N];
int n,m;
int dp[N][1 << 18];
int g[N][N],sum[N];
int vis[N];
vector<int> num,to[N];
void dfs(int pre,int pos,int state) {
int t = lower_bound(num.begin(),num.end(),c[pos]) - num.begin(); //state | t ???
if(vis[c[pos]] == 1) dp[pos][state] = dp[pre][state] + w[c[pos]];
else if(vis[c[pos]] >= 2 && (state & 1<<t) == 0) dp[pos][state | (1 << t)] = dp[pre][state] + w[c[pos]];
else if(vis[c[pos]] >= 2) dp[pos][state] = dp[pre][state];
if(vis[c[pos]] >= 2) sum[pos] = max(sum[pos],dp[pos][state | (1 << t)]);
else sum[pos] = max(sum[pos],dp[pos][state]);
for(auto v : to[pos]) {
if(v <= pos || v > n) continue;
if(vis[c[pos]] >= 2) dfs(pos,v,state | (1 << t));
else dfs(pos,v,state);
}
}
int main() {
cin >> n >> m;
for(int i=1; i<=n; i++) {
cin >> c[i];
if(vis[c[i]] == 1) num.push_back(c[i]);
vis[c[i]]++;
}
sort(num.begin(),num.end());
for(int i=1; i<=n; i++) cin >> w[i];
for(int i=1; i<=m; i++) {
int a,b;
scanf("%d%d",&a,&b);
g[a][b] = 1;
}
for(int i=1; i<=n; i++) {
for(int j=i+2; j<=n; j++) {
for(int k=i+1; k<=j-1; k++) {
if(g[i][j] && g[i][k] && g[k][j]) g[i][j] = 0;
}
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(g[i][j]) to[i].push_back(j);
}
}
dfs(0,1,0);
for(int i=1; i<=n; i++) cout<<sum[i]<<"\n";
return 0;
}
//拓扑dp P1113 杂务
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 2e6+9;
int head[N],numE,w[N];
int n;
int in[N],f[N];
queue<int> qu;
struct E
{
int next,to;
} e[N];
void add(int a,int b)
{
e[numE] = {head[a],b};
head[a] = numE++;
}
int main()
{
memset(head,-1,sizeof head);
cin >> n;
for(int i=1; i<=n; ++i)
{
int x,len,b;
scanf("%d%d",&x,&len);
w[x] = len;
while(~scanf("%d",&b),b)
{
add(x,b);
in[b]++;
}
}
int ans = 0;
for(int i=1; i<=n; i++) if(in[i] == 0) qu.push(i),f[i] = w[i];
while(!qu.empty())
{
auto t = qu.front();
qu.pop();
for(int i=head[t]; ~i; i=e[i].next)
{
int v = e[i].to;
if(--in[v] == 0)
{
qu.push(v);
}
f[v] = max(f[v],f[t] + w[v]);
}
}
for(int i=1; i<=n; i++) ans = max(ans,f[i]);
cout<<ans<<"\n";
return 0;
}
树形dp
https://ac.nowcoder.com/acm/contest/11223/D
循环遍历边即可！
#include <iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 2e6+9;
int a[N],e[N],ne[N],h[N],w[N];
int idx;
int dp[N][3];
void add(int a,int b,int c)
{
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(nullptr);
memset(h,-1,sizeof h);
int n;
cin >> n;
for(int i=2; i<=n; i++)
{
int fa,w;
cin >> fa >> w;
add(i,fa,w);
add(fa,i,w);
}
for(int i=1; i<=n; i++)
{
for(int j=h[i]; ~j; j=ne[j])
{
if(w[j] == 1) dp[i][1]++;
if(w[j] == 2) dp[i][2]++;
}
}
for(int i=1; i<=n; i++)
{
for(int j=h[i]; ~j; j=ne[j])
{
if(w[j] == 1) dp[i][2] += (dp[e[j]][1] - 1);
}
}
for(int i=1; i<=n; i++)
{
int ans = dp[i][1] + dp[i][2] + 1;
cout<<ans<<"\n";
}
return 0;
}
#include <iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 2e6 + 9;
vector<pair<int, int>> ve[N];
int dp[N][4];
int main()
{
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
for (int i = 2; i <= n; i++)
{
int father, w;
cin >> father >> w;
ve[father].push_back({ i, w });
ve[i].push_back({ father, w });
}
for (int i = 1; i <= n; i++)
{
for (auto [to, dist] : ve[i])
{
if (dist == 1) dp[i][1]++;
if (dist == 2) dp[i][2]++;
}
}
for (int i = 1; i <= n; i++)
{
for (auto [to, dist] : ve[i])
{
if (dist == 1) dp[i][2] += (dp[to][1] - 1);
}
}
for (int i = 1; i <= n; ++i)
{
int ans = dp[i][1] + dp[i][2] + 1;
cout << ans << "\n";
}
return 0;
}
https://ac.nowcoder.com/acm/contest/11222/E
邻接表存图
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 2e5+9;
int idx,e[N],ne[N],h[N],w[N];
int vis[N];
ll a[N],dp[N];
void add(int a,int b,int c)
{
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}
void dfs(int u)
{
vis[u] = 1;
dp[u] = a[u];
for(int i=h[u]; i!=-1; i=ne[i])
{
int j = e[i];
if(!vis[j])
{
dfs(j);
if(dp[j] + w[i] > 0) dp[u] += dp[j] + w[i];
//dp[i]指的是以i号节点为根的最大舒适度！
}
}
}
int main()
{
memset(h,-1,sizeof h);
idx = 0;
int n;
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<n; i++)
{
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);
add(b,a,c);
}
dfs(1);
ll ans = -1e9;
for(int i=1; i<=n; i++) ans = max(ans,dp[i]);
printf("%lld\n",ans);
return 0;
}
vector 存图
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 2e5+9;
ll a[N],dp[N];
int n;
vector<pair<int,ll>> ve[N];
void dfs(int now,int fa)
{
dp[now] = a[now];
for(auto [to,w] : ve[now])
{
if(to == fa) continue;
dfs(to,now);
if(dp[to] + w > 0) dp[now] += dp[to] + w;
}
}
int main()
{
cin >> n;
for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
for(int i=1; i<n; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
ve[a].push_back({b,c});
ve[b].push_back({a,c});
}
dfs(1,-1);
ll ans = -1e9;
for(int i=1; i<=n; i++) ans = max(ans,dp[i]);
printf("%lld\n",ans);
return 0;
}
线性dp
https://oj.neauacm.cn/problem.php?cid=1218&pid=6
输入
第一行输入两个数n和m。
接下来输入n个整数，代表每一个数的值。
数据范围：1≤n≤1000, 0≤ai≤999.
输出
输出一个整数，将至多m个数每个增加1后，数位中0的个数和的最大值。
3 2
9 99 999
5
5 3
399 369 609 90 539
6
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 2e3+9;
int a[N];
int n,m;
int dp[N][N];
int solve(int x)
{
int cnt = 0;
if(x == 0) return 1;
while(x)
{
int t = x%10;
if(t == 0) cnt++;
x /= 10;
}
return cnt;
}
int main()
{
ios_base :: sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> a[i];
int ans = 0;
for(int i=1; i<=n; i++) dp[i][0] = solve(a[i]) + dp[i-1][0];
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
dp[i][j] = max(dp[i-1][j-1] + solve(a[i]+1),dp[i-1][j] + solve(a[i]));
}
}
for(int i=0; i<=m; i++) ans = max(dp[n][i],ans);
cout<<ans<<"\n";
return 0;
}
//https://www.luogu.com.cn/problem/P1115
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5+9;
int dp[N],a[N];
int main()
{
int n;
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++)
{
dp[i] = max(dp[i-1]+a[i],a[i]); //以n结尾的最大连续子段和！
}
int ans = -2e9;
for(int i=1; i<=n; i++) ans = max(ans,dp[i]);
cout<<ans<<'\n';
return 0;
}
//https://oj.neauacm.cn/problem.php?cid=1199&pid=5
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e6+9;
int dp[N][3];
int a[N],b[N];
int main()
{
ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int t;
cin >> t;
while(t--)
{
memset(dp,0,sizeof dp);
int n;
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++) cin >> b[i];
int ans = 0x3f3f3f3f;
for(int i=1; i<=n; i++)
{
//每一步dp[i][0],dp[i][1],dp[i][2]都必须要有值！
dp[i][0] = min(min(dp[i-1][0],dp[i-1][1]),dp[i-1][2]) + 1;
if(a[i] == 1) dp[i][1] = min(dp[i-1][0],dp[i-1][2]);
else dp[i][1] = 0x3f3f3f3f;
if(b[i] == 1) dp[i][2] = min(dp[i-1][0],dp[i-1][1]);
else dp[i][2] = 0x3f3f3f3f;
}
ans = min(min(dp[n][0],dp[n][1]),dp[n][2]);
cout<<ans<<"\n";
}
return 0;
}
//https://ac.nowcoder.com/acm/contest/23106/A
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5+9;
long long mod = 998244353;
int n;
int a[N],dp[N][10];
int main()
{
ios_base :: sync_with_stdio(false); cin.tie(nullptr);
dp[0][0] = 1;
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++)
{
for(int j=0; j<=8; j++)
{
dp[i][(j+a[i])%9] = (dp[i][(j+a[i])%9] + dp[i-1][j]) % mod;
dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod;
}
}
// for(int i=1; i<=8; i++) cout<<dp[n][i]<<" ";
// cout<<dp[n][0] - 1<<"\n";
dp[n][0]--; //多算了一个dp[0][0];
for(int i=1; i<=9; i++) cout<<dp[n][i%9]<<" ";
return 0;
}
京公网安备 11010502036488号