2019 ICPC 银川 A. Girls Band Party(分组背包)

题意:

有n张卡片,每张卡片三个属性,name,color,value。
现在要打出5张卡片,要求名字不能相同(题目保证有解)。求最大的value和。
还有两个条件,题目给出五个名字,出现这些名字一次 加 10%的总分
以及给出一个color,出现一次这个color 加20%总分
求最大value

思路:

因为每个名字只能选一次。
所以可以用分组背包
把同一个名字的放在同一组进行枚举。
然后还有加成这一属性,也放到dp数组的状态里面去。
dp[i][j][k] 表示前i组 选了j张卡片 且 加成为k 时的最大值
最后从ans = max(dp[i][j][k])
(小细节没注意卡了好几个小时才找出来)

AC代码:
#include cstdio
#include vector
#include queue
#include cstring
#include cmath
#include map
#include set
#include stack
#include string
#include iostream
#include algorithm
#include iomanip
using namespace std;
#define sd(n) scanf("%d",n)
#define sdd(n,m) scanf("%d%d",n,m)
#define sddd(n,m,k) scanf("%d%d%d",n,m,k)
#define pd(n) printf("%d\n", n)
#define pc(n) printf("%c", n)
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",n)
#define sldd(n,m) scanf("%lld%lld",n,m)
#define slddd(n,m,k) scanf("%lld%lld%lld",n,m,k)
#define sf(n) scanf("%lf",n)
#define sc(n) scanf("%c",n)
#define sff(n,m) scanf("%lf%lf",n,m)
#define sfff(n,m,k) scanf("%lf%lf%lf",n,m,k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for(int i=a;i=n;i++)
#define per(i,a,n) for(int i=n;i=a;i--)
#define mem(a,n) memset(a, n, sizeof(a))
#define debug(x) cout  #x  ": "  x  endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mod(x) ((x)%MOD)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) (x-x)
#define pii mapint,int
#define mk make_pair
#define rtl rt1
#define rtr rt1|1
//#define int long long

typedef pairint,int PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
//const int inf = 0x3f3f3f3f;
inline int read(){int ret = 0, sgn = 1;char ch = getchar();
while(ch  '0' || ch  '9'){if(ch == '-')sgn = -1;ch = getchar();}
while (ch = '0'  ch = '9'){ret = ret*10 + ch - '0';ch = getchar();}
return ret*sgn;}
inline void Out(int a){if(a9) Out(a/10);putchar(a%10+'0');}
int qpow(int m, int k, int mod){int res=1,t=m;while(k){if(k1)res=res*t%mod;t=t*t%mod;k=1;}return res;}
ll gcd(ll a,ll b){return b==0?a : gcd(b,a%b);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll inv(ll x,ll m){return qpow(x,m-2,m)%m;}

const ll inf = -1e18;
const int N = 2e5+15;
ll dp[N][6][16];    // dp[i][j][k] 表示前i组选了j张时加成为k 的最大值
int n,m;
struct node{
    string name;
    string color;
    int val;
}a[N];
vectornode G[N];
mapstring,int group;
mapstring,int names;
mapstring,int colors;

signed main()
{
    int t = 1;
    cint;
    for(int j = 0;j  6; ++j)
        for(int i = 0;i  16; ++i)
            dp[0][j][i] = inf;
    dp[0][0][0] = 0;
    while(t--)
    {
        cinn;
        group.clear();
        names.clear();
        colors.clear();
        for(int i = 0 ; i = n ; i ++)
            G[i].clear();
        int cnt = 0;
        for(int i = 0 ; i  n ; i ++)
        {
            cina[i].namea[i].colora[i].val;
            if(group[a[i].name] == 0)
                group[a[i].name] = ++cnt;
            G[group[a[i].name]].pb(a[i]);
        }
        for(int i = 0 ; i  5; i ++)
        {
            string s;  cins;
            names[s] = 1;
        }
        string s;  cins;
        colors[s] = 2;
        for(int i = 1 ; i = cnt ; i ++)
        {
            for(int j = 0 ; j  6 ; j ++)
                for(int k = 0 ; k  16 ; k ++)
                    dp[i][j][k] = dp[i-1][j][k];
            for(int pos = 0 ; pos  G[i].size() ; pos ++)
            {
                int bonus = names[G[i][pos].name]+colors[G[i][pos].color];
                for(int j = 1 ; j = 5; j ++)
                {
                    for(int k = bonus ; k  16 ; k ++)
                    {
                        dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-bonus]+G[i][pos].val);
                    }
                }
            }
        }
        ll ans = 0;
        for(int i = 0 ; i  16 ; i ++)
        {
            if(dp[cnt][5][i]0)
                ans = max(ans,dp[cnt][5][i]*(10+i)/10);
        }
        coutansendl;
    }
}

最新回复(0)
/jishu3L0_2FnGrPWTzuQ0YF7hF_2BOrvmzkU_2Ft_2FbkhRcnZYpFeeg_3D4834405
8 简首页