洛谷动态规划题单

P2196 [NOIP1996 提高组] 挖地雷

https://www.luogu.com.cn/problem/P2196 普及/提高−

这一道题直接用dfs就能做，不需要动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const int inf = 2147483647;
const ll INF = 1e18;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n+1);
    vector<vector<int>>adj(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n-1;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int x;
            cin>>x;
            if(x)
            {
                adj[i].push_back(j);// 这个是单向边
            }
        }
    }    
    vector<int>ret;
    ll ans=0;
    vector<ll>dp(n+1);
    ll sum=0;
    auto dfs=[&](auto self,int u,int fa,vector<int>&vv)->void{
        if(adj[u].empty())//搜到底部的话如果总和(sum>ans),那么就更新ans和存的路径数组ret
        {
            if(sum>ans){ret=vv;ans=sum;}
            return;
        }
        for(auto v:adj[u])
        {
            if(v==fa)continue;
            vv.push_back(v);
            sum+=a[v];
            self(self,v,u,vv);
            vv.pop_back();
            sum-=a[v];
        }
    };
    for(int i=1;i<=n;i++)
    {
        sum=0;
        vector<int>vv;
        vv.push_back(i);//将路径的第一个点线计算进去
        sum+=a[i];
        dfs(dfs,i,-1,vv);
    }
    for(int i=0;i<ret.size();i++)cout<<ret[i]<<" \n"[i==ret.size()-1];
    cout<<ans<<'\n';
    return 0;    
}

P1434 [SHOI2002] 滑雪

https://www.luogu.com.cn/problem/P1434 普及/提高−

这一题求滑雪的最大路径,我的理解是对每一个点进行dfs, 找到能走到的尽头, 然后回溯从1递增赋值,同时对路径上的每一个点进行标记( vis数组 ), 如果在dfs的过程中遇到已标记的点, 那么就直接回溯, 对这个点进行递增.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const int inf = 2147483647;
const ll INF = 1e18;
int dx[]={1,0,0,-1};
int dy[]={0,1,-1,0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>a(n+1,vector<int>(m+1)),vis(n+1,vector<int>(m+1)),dp(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)cin>>a[i][j];
    }    
    int jishu=0;
    auto dfs=[&](auto self,int x,int y)->void{
        int cnt=0;
        vis[x][y]=1;
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i],yy=y+dy[i];
            if(xx<1||xx>n||yy<1||yy>m)continue;
            if(a[xx][yy]<=a[x][y])continue;
            cnt++;
            if(vis[xx][yy]){dp[x][y]=max(dp[x][y],dp[xx][yy]+1);continue;}// r如果标记了, 就直接回溯然后递增
            self(self,xx,yy);
            dp[x][y]=max(dp[x][y],dp[xx][yy]+1);
        }
        if(!cnt)dp[x][y]=1;如果无路可通, 说明是最下面那一个点, 就从1开始赋值.
    };
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(vis[i][j])continue;//没走过可以走
            dfs(dfs,i,j);
        }
    }
    int maxn=-inf;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)maxn=max(maxn,dp[i][j]);
    }
    cout<<maxn<<'\n'; 
    return 0;    
}

P4017 最大食物链计数

https://www.luogu.com.cn/problem/P4017 普及/提高−

拓扑排序, 在走到每一个链走后一个点时用ret进行累加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
using ll = long long;
using u64 = unsigned long long;
const int inf = 2147483647;
const ll INF = 1e18;
const int mod=80112002;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>adj(n+1);
    vector<int>in(n+1);
    for(int i=1;i<=m;i++)    
    {
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        in[b]++;
    }
    queue<int>q;
    vector<int>sum(n+1);
    for(int i=1;i<=n;i++)
    {
        if(in[i]==0){q.push(i);sum[i]=1;}
    }
    int ret=0;
    while(q.size())
    {
        int shu=q.front();q.pop();
        if(adj[shu].empty())ret+=sum[shu];
        for(auto v:adj[shu])
        {
            sum[v]=(sum[shu]+sum[v])%mod;
            if(--in[v]==0)q.push(v);
        }
    }
    cout<<ret%mod<<'\n';
    return 0;    
}

P1115 最大子段和

https://www.luogu.com.cn/problem/P1115 普及−

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
const int N=2e5+10;
int arr[N];
int main()
{
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    vector<int>dp(n+1);
    for(int i=1;i<=n;i++)
    {
        if(dp[i-1]>0)dp[i]=dp[i-1]+arr[i];
        else dp[i]=arr[i];
    }
    int ret=*max_element(dp.begin()+1,dp.end());
    cout<<ret<<"\n";



    return 0;    
}

P1077 [NOIP2012 普及组] 摆花

https://www.luogu.com.cn/problem/P1077 普及/提高−

这个是多重背包，但是由于每次消耗的都是1，所以看起来比较简单，为了便于理解，这里也附上oiwiki上的多重背包代码

1
2
3
4
5
6
7
8
for (int i = 1; i <= n; i++) {
  for (int weight = W; weight >= w[i]; weight--) {
    // 多遍历一层物品数量
    for (int k = 1; k * w[i] <= weight && k <= cnt[i]; k++) {
      dp[weight] = max(dp[weight], dp[weight - k * w[i]] + k * v[i]);
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const int inf = 2147483647;
const ll INF = 1e18;
const int mod=1e6+7;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<int>dp(m+1);
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=1;j--)
        {
            for(int k=1;k<=min(a[i],j);k++)
            {
                dp[j]=(dp[j]+dp[j-k])%mod;
            }
        }
    }
    cout<<dp[m]<<'\n';
    return 0;    
}

P3842 [TJOI2007] 线段

https://www.luogu.com.cn/problem/P3842 普及/提高−

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const int inf = 2147483647;
const ll INF = 1e18;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<vector<int>>dp(n+1,vector<int>(2));// 背包开了两维，第二维如果是0就是线段的左端点，1就是线段的右端点
    dp[0][0]=0,dp[0][1]=0;
    vector<pair<int,int>>v(n+1);
    v[0].first=1,v[0].second=1;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].first>>v[i].second;
        auto [l,r]=v[i-1];
        auto [ll,rr]=v[i];
        // 每一层的左右两个端点都可以从上一层的左右两个端点递推而来
        dp[i][0]=min(dp[i-1][0]+abs(rr-l)+rr-ll,dp[i-1][1]+abs(rr-r)+rr-ll);
        dp[i][1]=min(dp[i-1][0]+abs(ll-l)+rr-ll,dp[i-1][1]+abs(ll-r)+rr-ll);
    }    
    cout<<min(dp[n][0]+abs(n-v[n].first),dp[n][1]+abs(n-v[n].second))+n-1<<'\n';// 记得还要加上n-1，因为每走一层要+1
    return 0;    
}

P1064 [NOIP2006 提高组] 金明的预算方案

https://www.luogu.com.cn/problem/P1064 普及+/提高

总的来说感觉还是0/1背包，只不过需要分情况，将主键和附件绑定到一起的各种情况分别计算就行了

1
2
3
4
5
6
7
8
9
10
11
这个题的决策是五个，分别是：

1.不选，然后去考虑下一个 // 这种情况实操不用考虑，因为一维dp数组直接就相当于继承上一层了，这一种情况默认就已经完成了

2.选且只选这个主件

3.选这个主件，并且选附件1

4.选这个主件，并且选附件2

5.选这个主件，并且选附件1和附件2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const int inf = 2147483647;
const ll INF = 1e18;
struct node
{
    int v,p,q;
    int jz;
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,n;
    cin>>m>>n;
    vector<node>v(n+1);
    vector<vector<int>>adj(n+1);
    vector<ll>dp(m+1);
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].v>>v[i].p>>v[i].q;
        v[i].jz=v[i].v*v[i].p;
        if(v[i].q)adj[v[i].q].push_back(i);// 如果不是0的话就把他接到adj[v[i].q]后面
    }    
    for(int i=1;i<=n;i++)
    {
        if(v[i].q)continue;
        for(int j=m;j>=v[i].v;j--)
        {
            dp[j]=max(dp[j],dp[j-v[i].v]+v[i].jz);
            if(adj[i].size()==2)
            {
                if(j>=v[i].v+v[adj[i][0]].v)dp[j]=max(dp[j],dp[j-v[i].v-v[adj[i][0]].v]+v[i].jz+v[adj[i][0]].jz);

                if(j>=v[i].v+v[adj[i][0]].v+v[adj[i][1]].v)dp[j]=max(dp[j],dp[j-v[i].v-v[adj[i][0]].v-v[adj[i][1]].v]+v[i].jz+v[adj[i][0]].jz+v[adj[i][1]].jz);

                if(j>=v[i].v+v[adj[i][1]].v)dp[j]=max(dp[j],dp[j-v[i].v-v[adj[i][1]].v]+v[i].jz+v[adj[i][1]].jz);
                
            }
            else if(adj[i].size()==1)
            {
                if(j>=v[i].v+v[adj[i][0]].v)dp[j]=max(dp[j],dp[j-v[i].v-v[adj[i][0]].v]+v[i].jz+v[adj[i][0]].jz);
            }
        }
        
    }
    cout<<dp[m]<<'\n';
    return 0;    
}