Codeforces GYM 100753J: Souvenirs 题解

78 阅读 0 评论 52 点赞

我是靠谱客的博主哭泣咖啡，最近开发中收集的这篇文章主要介绍Codeforces GYM 100753J: Souvenirs 题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这题是显然的dp

设dp[i][j][k]为考虑到第i个商人（第i个商人已经处理完），当前有j个金币和k个银币时，最多能买到多少纪念品

1.不买第i个纪念品，dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k])

2.用金币买第i个纪念品，dp[i][j][k]=max(dp[i][j][k],dp[i-1][j+1][k-get*pack[i]]+1)

get指的是通过商人的种类算出的商人会给你的钱袋数,pack[i]表示第i个商人一个钱袋里装多少银币

当k-get*pack[i]>=price[i]且第i个商人是generous时，不能用金币购买

3.用银币买第i个纪念品，dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k+price[i]]+1)

注意数组要滚动

我做这题的时候总是TLE，后来发现在循环里判断s[i]=="generous","greedy","honest"非常慢，因为是字符串的比较

所以提前把类型转换成数字后判断效率提升8倍左右

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <utility>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#define Pair pair<int,int>
#define LOWBIT(x) x & (-x)
#define LL long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
using namespace std;
const int MOD=1e9+7;
const int INF=0x7ffffff;
const int magic=348;
const double eps=1e-9;
int g,c,n;
string s[101];
int type[101];
int pack[101],price[101];
int dp[2][101][20148];
int main ()
{
int i,j,k;
scanf("%d%d%d",&g,&c,&n);
for (i=1;i<=n;i++)
{
cin>>s[i]>>pack[i]>>price[i];
if (s[i]=="generous") type[i]=1;
if (s[i]=="greedy") type[i]=2;
if (s[i]=="honest") type[i]=3;
}
for (i=0;i<=1;i++)
for (j=0;j<=c;j++)
for (k=0;k<=20100;k++)
dp[i][j][k]=-INF;
dp[0][c][0]=0;
int p1=0,p2=1;
int remain,get;
double t;
int ans=0;
for (i=1;i<=n;i++)
{
for (j=0;j<=c;j++)
for (k=0;k<=min(i*100,10010);k++)
{
dp[p2][j][k]=dp[p1][j][k];
/*if (k+price[i]<=20100)
{
dp[p2][j][k]=max(dp[p2][j][k],dp[p1][j][k+price[i]]+1);
if (type[i]==1 && dp[p1][j][k+price[i]]>=0)
{
if (i==n) ans=max(ans,dp[p2][j][k]);
continue;
}
}*/
remain=g-price[i];
t=remain*1.0/pack[i];
if (type[i]==2) get=int(t);
if (type[i]==3) get=int(t+0.5);
if (type[i]==1)
{
get=int(t+1);
if (t==int(t)) get--;
}
if (j+1<=c && k-get*pack[i]>=0)
if (!(type[i]==1 && k-get*pack[i]>=price[i]))dp[p2][j][k]=max(dp[p2][j][k],dp[p1][j+1][k-get*pack[i]]+1);
if (k+price[i]<=min(i*100,10010))
dp[p2][j][k]=max(dp[p2][j][k],dp[p1][j][k+price[i]]+1);
if (i==n) ans=max(ans,dp[p2][j][k]);
}
p1^=1;p2^=1;
}
printf("%dn",ans);
return 0;
}