Codeforces Round #510 #B

6903 ワード

http://codeforces.com/contest/1042/problem/B
 
タイトル:
n種類の飲み物を与えて、すべての飲み物は1種あるいは多種のビタミン(AあるいはBあるいはC)があって、ある人は3種類のビタミンを集めたいと思って、最低でいくらかかりますか?
各行はまず各飲料の価格を入力し、各飲料に含まれるビタミンの種類を入力します.
 
ABCをそれぞれ1つの数字で表し、開始時に準備:1はA、2はB、3はCを表す.
ビタミンAを含む飲料=1、ビタミンBを含む=2、C=3、AB=A+B=3となっていますが、これは間違いで、重複しています.
だから私たちは3つの質量数でABCを表したほうがいいです.
ここでA=2,B=5,C=11である.
AB=A*B=10,AC=A*C=22,BC=B*C=55;
ABC=110.
もちろんここはプラス表示でもいいので、気分次第です.
では、入力時に、飲料ごとに最小値を記録し、3つのビタミンが現れたかどうかを判断する必要があります.
では、私たちの答えは$min{AB+C,AC+B,BC+A,A+B+C,AC+BC,AB+BC,AB+AC}$$です.
もちろん答えを判断するときは、この飲み物が現れたかどうかを判断する必要があります.
!!!奇抜な方法ほどhackされにくい.
#include 
#include 
#include 
#include 
#include 
using namespace std;
int p[100000],ans,cnt;
int n,val[1006],cost,a[222];        //A=2,B=5,C=11;
char s[4];
bool vis[1100],hack[100000];        //hack             。 
int main()
{
    ans=2147483647;
    a['A']=2;a['B']=5;a['C']=11;
    memset(p,0x7f,sizeof(p));
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&cost);
        scanf("%s",s);
        int l=strlen(s),tot=1;
        for(int j=0; j)
        {
            tot*=a[s[j]];
            if(!vis[s[j]])vis[s[j]]=1,cnt++;
        }
        p[tot]=min(p[tot],cost);
        hack[tot]=1;
    }
    if(cnt<3)printf("-1");
    else
    {
        
        if(hack[2]&&hack[5]&&hack[11])ans=min(ans,p[2]+p[5]+p[11]);
        if(hack[10]&&hack[11])ans=min(ans,p[10]+p[11]);
        if(hack[22]&&hack[5])ans=min(ans,p[22]+p[5]);
        if(hack[55]&&hack[2])ans=min(ans,p[55]+p[2]);
        if(hack[110])ans=min(ans,p[110]);
        if(hack[10]&&hack[55])ans=min(ans,p[10]+p[55]);
        if(hack[22]&&hack[55])ans=min(ans,p[22]+p[55]);
        if(hack[10]&&hack[22])ans=min(ans,p[10]+p[22]);
        printf("%d",ans);
    }

}

 
転載先:https://www.cnblogs.com/rmy020718/p/9667668.html