UVALive 4260 Fortune Card Game (Regionals 2008 Asia Taipei +DP)
[제목 대의]:
A popular card game called ``fortune"is getting popular in country X. Fig. 1 shows one of the cards. In each card, a positive integer number (20 in the figure) is listed as the address of the card. A symbol is drawn beside the address. There are five kinds of symbols, which are listed below the card. For convenience, let each symbol be represented by an English letter from `A'-`E'. The bottom of a card contains another number called ``next fortune number."
Figure 1: A sample fortune card and symbols.
In a set of fortune cards, many cards can have same address; that is, address 20 is not limited to appear only in one card. However, there will be no cards that are identical, i.e., no two cards with same address, symbol, and next fortune number.
The fortune card game is played as follows. A player starts with cards that have address 1. The goal of the game is trying to complete a ``spell"that is composed by the symbols. For example, let a spell be ``BADDAD". In the first move, the player will look for cards that have address 1 with a star symbol (which matches `B' in the spell). The next fortune numbers of these cards are the new addresses for the next move. The player can select one card to advance to a new address x. The selected card is then put back to the cards for next move but the fortune number is written down.
Let the example be continued. In the next move, the player needs to look for the cards that have new address x with the cross symbol (which matches the second `A' in the spell). Again, the player selects one card to advance to another new address. This procedure continues until the spell ``BADDAD"is completed. Once the player completes a spell, he wins a score by adding all the next fortune numbers of the selected card, which have been written down.
Given a spell and a set of fortune cards, please output the maximum score that can be played in this card game.
Technical Specification
Input
Test data begins with an integer N which is the number of test cases. Each test case begins with an integer C, which is the number of cards. Following the number C is C lines of card information. Each card is represented by (Address Symbol NextF ortuneNumber). The address and next fortune number are between 1 and 800. The symbols are capital letters from `A' to `E'. The last line of a test case is a spell. The spell is a string composed by capital letters from `A' to `E'. The length of the spell (L ) is less than 150.
Output
For each test case, please output the maximum score that can be collected for each test case.
Sample Input
2
7
1 A 2
1 A 3
2 A 3
2 B 4
2 B 5
3 A 3
3 B 4
AAAAB
6
1 A 2
1 B 2
1 A 3
1 B 3
2 A 3
2 B 3
AB
Sample Output
16
5
【제목 대의】: 유저가 카드 게임을 제어하고 n장의 카드를 제어한다. 한 장에 세 가지 속성이 있다. ai: 주소, s: 카드 자모,bi: 카드 가치는 고정된spell 병음 자모 서열을 주고 모든 병음 자모 서열을 집적하여 얻을 수 있는 최대 가치를 구한다. 규칙은 한 장의 카드를 선택하면 이 카드의 가치 속성은 다음에 찾는 카드의 주소 속성이 된다.
【사고방식】 시합할 때 문제를 너무 급하게 읽고 일부 관건적인 부분을 제대로 파악하지 못해서 마지막에 오래 테스트했다. 시합 후에 사실은 더욱 간단하고 폭력적인 방법이 있었다. dp[i][j]를 정의했다. 이것은 i번째 카드 속성이 j의 최대 가치라는 것을 의미하고 점차적인 관계가 있다. dp[i][st[j].bi]=max(dp[i][st[j].bi],dp[i-1][st[j].ai]+st[j].bi);
The next fortune numbers of these cards are the new addresses for the next move
이 말은 선택한 카드의 가치 속성을 다음 카드의 주소로 하고 관건적인 해석은 dp[i-1][st[j]이다.ai]+st[j].bi 이 상태 이동
코드:
/*
* Problem: UVALive 4260
* Running time: 46MS
* Complier: G++
* Author: javaherongwei
* Create Time: 20:16 2015/10/14
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
const int inf=0x3f3f3f3f;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
struct node
{
int ai,bi;
char s;
} st[maxn];
string str;
int dp[maxn][maxn];
int main()
{
//freopen("2.txt","r",stdin);
int t;cin>>t;
while(t--)
{
int n;cin>>n;
for(int i=1; i<=n; ++i){
cin>>st[i].ai>>st[i].s>>st[i].bi;
}
cin>>str;
int len=str.size();
memset(dp,-inf,sizeof(dp));
dp[0][1]=0;///dp[i][j]: i j
for(int i=1; i<=len; ++i){///
for(int j=1; j<=n; ++j){/// j
if(st[j].s!=str[i-1]) continue;/// spell ,continue
dp[i][st[j].bi]=max(dp[i][st[j].bi],dp[i-1][st[j].ai]+st[j].bi);
// cout<<"dp[i][j]= "<<dp[i][j]<<endl;
}
}
int ans=0;
for(int i=1; i<=n; ++i)
ans=max(ans,dp[len][i]);
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #670(Div.2) 문제 해결먼저 하나의 서열을 어떻게 하강하지 않고 상승하지 않는 서열로 분해할 것인가를 고려해라.감법만 해서 이 서열을 상승하지 않는 서열로 바꾸는 것을 고려하면, 최대치가 이전 서열의 최소치와 같을 때까지 모든 극장 불하강...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.