NC231128 Steadily Growing Steam

题目链接

关键点：

1、题目要求求在n张牌中，可以对齐中的k张牌的点数翻倍的条件下，分成点数相同的两堆，两队中取的价值总和最大

2、设dp[i][j][k]表示从前i张牌中，用j次技能（翻倍点数），两个集合点数相差k的情况下的最大价值，k的取值范围为(-2600,2600),有 负数，我们将其都加上2600，那么就为k(0,5200)，因此所求的答案就为dp[n][k][2600];（k为使用技能的总次数）

3、转移情况总共有四种(以下采用了滚动数组)：

1、将当前牌加入A集合，不使用技能，要判断k+t[i]<=5200(k为当前点数差,以下均为)

dp[i%2][j][k] = max(dp[i%2][j][k], dp[(i-1)%2][j][k+t[i]]+v[i]);

2、将当前牌加入B集合，不使用技能，要判断k-t[i]>=0

dp[i%2][j][k] = max(dp[i%2][j][k], dp[(i-1)%2][j][k-t[i]]+v[i]);

3、取当前牌，放入B集合，用技能，要判断k-t[i]*2>=0&&j（j不能为0）

dp[i%2][j][k] = max(dp[i%2][j][k], dp[(i-1)%2][j-1][k-2*t[i]]+v[i]);

4、取当前牌，放入A集合，用技能，要判断k+t[i]*2<=5200&&j

dp[i%2][j][k] = max(dp[i%2][j][k], dp[(i-1)%2][j-1][k+t[i]*2]+v[i]);

最后在这些中取最大值即可

完整代码：

# include <bits/stdc++.h>
using namespace std;
int n, k;
long long dp[2][110][5210];//前i个物品，用了j次技能，两个集合相差k的最大价值
int v[110], t[110];
int main()
{
    cin>>n>>k;
    for (int i=1; i<=n; i++)
    {
        cin>>v[i]>>t[i];
    }
    for (int i=0; i<=k; i++)
    {
        for (int j=0; j<=5200; j++)
            if (j!=2600)
            dp[0][i][j] = -1e18;
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=0; j<=k; j++)
        {
            for (int k=0; k<=5200; k++)
            {
                dp[i%2][j][k] = dp[(i-1)%2][j][k];//不取当前牌
                if (k+t[i]<=5200)//取当前牌，放入A集合，不用技能
                    dp[i%2][j][k] = max(dp[i%2][j][k], dp[(i-1)%2][j][k+t[i]]+v[i]);
                if (k-t[i]>=0)//取当前牌，放入B集合，不用技能
                    dp[i%2][j][k] = max(dp[i%2][j][k], dp[(i-1)%2][j][k-t[i]]+v[i]);
                if (k-t[i]*2>=0&&j)//取当前牌，放入B集合，用技能
                    dp[i%2][j][k] = max(dp[i%2][j][k], dp[(i-1)%2][j-1][k-2*t[i]]+v[i]);
                if (k+t[i]*2<=5200&&j)//取当前牌，放入A集合，用技能
                    dp[i%2][j][k] = max(dp[i%2][j][k], dp[(i-1)%2][j-1][k+t[i]*2]+v[i]);
                    
            }
        }
    }
    cout<<dp[n%2][k][2600]<<endl;
    
    return 0;
}

NC21467 [NOIP2018]货币系统

题目链接

关键点：

1、本题要求求给出一个数列，求是否能使数组内的数可以互相表示，减少数组的数量，求这个最少的数量

2、用bool数组dp[i]表示i元是否能被表示，动态转移方程：dp[j] = dp[j] | dp [j-a[i]]; 因为一个货币可以使用多次，因此用一维数组，顺着遍历价值，就可以实现

3、如果一个币的价值，在开始用他组成价值前，已经被其他硬币表示，那么就可以去掉这个硬币

完整代码：

# include <bits/stdc++.h>
using namespace std;
int t, n;
int a[110];
bool dp[25000+10];
int main()
{
    cin>>t;
    while (t--)
    {
        cin>>n;
        int ans = n;
        for (int i=1; i<=n; i++)
            cin>>a[i];
        sort(a+1, a+1+n);
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int i=1; i<=n; i++)
        {
            if (dp[a[i]])
            {
                ans--;
                continue;
            }
            for (int j=a[i]; j<=a[n]; j++)
            {
                dp[j] = dp[j]|dp[j-a[i]]; 
            }
        }
        cout<<ans<<endl;
    }
    
    return 0;
}

NC235950 多重背包

题目链接

关键点：

1、一个物品有多件，将第i种物品分成若干见物品，其中每件物品有一个系数，这些物品的费用和价值均是原来的费用和价值乘以这个系数，使这些系数为

1，2，4，……2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数，例如n[i]=13,则将这些物品分成1,2,4,6四件物品

完整代码：

# include <bits/stdc++.h>
using namespace std;
int n, t;
int x1, w1, v1, k, cnt;
int w[2010], v[2010];
int dp[2000+10];
int main()
{
    cin>>n>>t;
    for (int i=1; i<=n; i++)
    {
        cin>>x1>>w1>>v1;
        k = 1;
        while (k<=x1)
        {
            cnt++;
            w[cnt] = k*w1;
            v[cnt] = k*v1;
            x1-=k;
            k*=2;
        }
        if (x1>0)
        {
            cnt++;
            w[cnt] = x1*w1;
            v[cnt] = x1*v1;
        }
    }
    
    
    for (int i=1; i<=cnt; i++)
    {
        for (int k=t; k>=w[i]; k--)
        {
            dp[k] = max(dp[k], dp[k-w[i]]+v[i]);
        }
    }
    
    cout<<dp[t]<<endl;
    
    
    return 0;
}