9/7 dp练习+01背包方案数+求背包具体方案

01背包方案数

在f[j]表示容量为j时可获得的最大价值的情况下，增加数组c[i]表示容量为i时最优选法的方案数

void fun()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            if(f[j-v[i]]+w[i]>f[j])
            {
                f[j]=f[j-v[i]]+w[i];
                c[j]=c[j-v[i]];
            }
            else if(f[j-v[i]]+w[i]==f[j])
                c[j]=(c[j]+c[j-v[i]])%mod;
        }
    }
    cout<<c[m]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

若增加条件，恰好装满背包的最大价值的方案数？
只需要改变初始化条件即可：
只有恰好装满时，才能直接或间接通过c[0]转移

    for(int i=1;i<=n;i++)
        f[i]=-inf;
    f[0]=0,c[0]=1;
1
2
3

求背包具体方案

void fun()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    for(int n;i>=1;i--)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i+1][j];
            if(j>=v[i])
                f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
        }
    }
    int j=m;
    for(int i=1;i<=n;i++)
    {
        if(j>=v[i]&&f[i][j]==f[i][j-v[i]]+w[i])
        {
            cout<<i<<" ";
            j-=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

例题：
P1759 通天之潜水

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=1e5+5;
const int inf=1e18;
const int mod=19980829;
int m,v,n,a[105],b[105],c[105],f[105][205][205];

void solve()
{
    cin>>m>>v>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i]>>c[i];
    for(int i=n;i>=1;i--)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=v;k++)
            {
                f[i][j][k]=f[i+1][j][k];
                if(j>=a[i]&&k>=b[i])
                    f[i][j][k]=max(f[i][j][k],f[i+1][j-a[i]][k-b[i]]+c[i]);
            }
        }
    }
    cout<<f[1][m][v]<<endl;
    int g=m,k=v;
    for(int i=1;i<=n;i++)
    {
        if(g>=a[i]&&k>=b[i]&&f[i][g][k]==f[i+1][g-a[i]][k-b[i]]+c[i])
        {
            cout<<i<<" ";g-=a[i],k-=b[i];
        }
    }
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}
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

P1122 最大子树和

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=1e6+5;
const int inf=1e18;
const int mod=19980829;
int n,cnt,head[N],a[N],f[N];
struct node
{
    int to,nxt;
}e[N*2];
void add(int from,int to)
{
    e[++cnt].to=to;
    //e[cnt].w=w;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
void dfs(int u,int fa)
{
    f[u]=a[u];
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        if(f[v]>0)
            f[u]=f[u]+f[v];
    }
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        add(u,v),add(v,u);
    }
    dfs(1,0);
    int ans=-inf;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i]);
    cout<<ans<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

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

P1140 相似基因

思路：
1.设计状态：f[i][]j]表示s1前i个字母和s2前j个字母的最大价值是多少
2.状态转移:s1第i个字母对应s2第j个字母、s1第i个字母对应s2中用_对应、s1中用_对应s2第j个字母

f[i][j]=max({f[i-1][j-1]+d[a[i]][b[j]],f[i-1][j]+d[a[i]][5],f[i][j-1]+d[5][b[j]]});
1

3.将4个字母转移为数字1、2、3、4，打表表示对应关系

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=1e5+5;
const int inf=1e18;
const int mod=19980829;
int n,m,a[105],b[105],f[105][105];
string s1,s2;
int d[6][6]={{0,0,0,0,0,0},
             {0,5,-1,-2,-1,-3},
             {0,-1,5,-3,-2,-4},
             {0,-2,-3,5,-2,-2},
             {0,-1,-2,-2,5,-1},
             {0,-3,-4,-2,-1,0}
             };
void solve()
{
    cin>>n>>s1>>m>>s2;
    for(int i=1;i<=n;i++)
    {
        if(s1[i-1]=='A') a[i]=1;
        else if(s1[i-1]=='C') a[i]=2;
        else if(s1[i-1]=='G') a[i]=3;
        else a[i]=4;
    }
    for(int i=1;i<=m;i++)
    {
        if(s2[i-1]=='A') b[i]=1;
        else if(s2[i-1]=='C') b[i]=2;
        else if(s2[i-1]=='G') b[i]=3;
        else b[i]=4;
    }
    for(int i=1;i<=n;i++)
        f[i][0]=f[i-1][0]+d[a[i]][5];
    for(int i=1;i<=m;i++)
        f[0][i]=f[0][i-1]+d[5][b[i]];
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        f[i][j]=max({f[i-1][j-1]+d[a[i]][b[j]],f[i-1][j]+d[a[i]][5],f[i][j-1]+d[5][b[j]]});
    }
    cout<<f[n][m]<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

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

P1564 膜拜

思路：
1.可想到1和2的人数可抵消，因此将2转化为-1，使用前缀和记录。
2.若abs(sum[i]-sum[j-1])==i-j+1说明有连续的人数，若abs(sum[i]-sum[j-1])<=m也符合题意
3.转移方程:f[i]=min(f[i],f[j-1]+1)

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=1e5+5;
const int inf=1e18;
const int mod=19980829;
int n,m,sum[N],f[N];

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        if(x==1) sum[i]=sum[i-1]+1;
        else sum[i]=sum[i-1]-1;
        f[i]=inf;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if(abs(sum[i]-sum[j-1])==i-j+1||abs(sum[i]-sum[j-1])<=m)
                f[i]=min(f[i],f[j-1]+1);
        }
    }
    cout<<f[n]<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

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

P1806 跑步

类似于01背包，多加了一个条件，下一圈跑的圈数一定比上一圈多，对于每次跑的圈数，都可选可不选，最后减去1次，因为不可一次全跑完。

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=1e5+5;
const int inf=1e18;
const int mod=19980829;
int n,m,a[N],f[N];

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
       a[i]=i;
    f[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=n;j>=a[i];j--)
        f[j]+=f[j-a[i]];
    cout<<f[n]-1<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

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

P1922 女仆咖啡厅桌游吧

统计叶子节点的方法：只有一条边和其相连。
ps：在树的数据结构中，不存在出度、入度的关系

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=1e5+5;
const int inf=1e18;
const int mod=19980829;
int m,v,n,dp[N],d[N];
vector<int>e[N];
void dfs(int u,int fa)
{
    int ct=1;
    for(int v:e[u])
    {
        if(v==fa) continue;
        dfs(v,u);
        if(d[v]==1) ct++;
        else
            dp[u]+=dp[v];
    }
    dp[u]+=ct/2;
}
void solve()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
        d[u]++,d[v]++;
    }
    dfs(1,0);
    cout<<dp[1]<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

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

121. 买卖股票的最佳时机

#include
int a[1000005];
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        for(int i=0;i<n;i++)
            a[i+1]=prices[i];
        int mx=0,mi=1e9;
        for(int i=1;i<=n;i++)
        {
            mx=max(mx,a[i]-mi);
            mi=min(mi,a[i]);
        }
        return mx;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

122. 买卖股票的最佳时机 II

#include

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int dp[n+5][2],a[n+5];
        memset(dp,0,sizeof dp);
        memset(a,0,sizeof a);
        for(int i=0;i<n;i++)
            a[i+1]=prices[i];
        dp[1][0]=0;
        dp[1][1]-=a[1];
        for(int i=2;i<=n;i++)
        {
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-a[i]);
        }
        return dp[n][0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21