程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVa10654The Uxuhul Voting System

UVa10654The Uxuhul Voting System

編輯:C++入門知識

Problem D
The Uxuhul Voting System
Input:
standard input
Output: standard output
Time Limit: 1 second

One of the world's first civilizations was that of the ancient Uxuhul indians, in the jungles of Central America. The Uxuhul culture flourished for almost a thousand years, with its golden era around 3200 BC. Each year high priests, representing different parts of the realm, gathered in the capital to vote on important matters. There were always exactly three issues to vote on, and each issue was a simple yes/no question. The three issues were all decided in one single voting round, in the following manner:

All the priests would gather in a large room, with a table in the centre. On the table lie three flat stones, each with one white, and one black side. Each stone represented an issue, with the black side up symbolising the outcome'no' and the white side the outcome 'yes'. Initially all stones had the black side up, representing negative outcome on all issues. In order of age, from youngest to oldest, each priest voted, by turning exactly one stone, thus (temporarily) changing the outcome of one issue. It was not allowed to skip the vote, each priest had to flip a stone. The colours of the side facing up on the stones after the oldest priest had flipped the stone of his choice, determined the final outcome of the voting on the three issues.

The Uxuhul political life was rather complex, with a lot of lobbying by different interest groups. Lobbying (and bribery), gave each priest preferences between the eight different outcomes of the three issues. Religious rules forced each priest to publicly state his preference order between the eight outcomes, before the voting process started. Based on knowledge of each other priest's preferences, it was possible for the priests to choose a stone to flip in the way that it gained their interest best. As the Uxuhul were advanced logicians, with deep knowledge of game theory, each priest was actually able to vote in the optimal way!

Eventually, the complexity and rigidity of their political system brought the Uxuhul culture to collapse. Today only ruins remain of their cities and temples. Historians and archaeologists try to understand more about their history by studying the results from their yearly votes. However, only records of the priests' preferences remain, not the actual outcomes of the votes. Now it is your task to find a way to recover the outcomes.

Input

The input begins with an integer n, 1, the number of voting rounds. Starting on the next line, n problems follow, one by one. Each voting starts with a line containing an integer m, 1, stating the number of voting priests. Then there are m lines, defining the preference order for the outcomes of the three issues for each voter, in order, starting with the voter who will begin the voting procedure. The preferences for each outcome (NNN,NNY, NYN, NYY, YNN, YNY, YYN, and YYY respectively, where ‘N’ stands for no and ‘Y’ for yes), are given as an integer in the range [1…8]. Lower numbers indicate higher preference. The preferences for the eight outcomes are given in the same order as the enumeration of the outcomes above.

Output

For each of the n voting problems, output one line describing the outcome of the votes for the three issues, 'Y' for yes, and 'N' for no.

Sample Input Output for Sample Input

2

4

8 7 6 5 4 3 2 1

8 6 3 1 2 4 5 7

8 3 6 5 1 2 7 4

1 2 3 4 5 6 7 8

1

1 2 3 4 5 6 7 8

NYY

NNY



一道很水的dp題,用記憶化DP可以非常清晰地分析清楚狀態

dp(dep,statu) = min(三種後續狀態)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 100+10;
const int INF = 1e9;
int mat[maxn][8];
int dp[maxn][8];
map tma;
int m;
int dfs(int dep,int statu){
    if(dep==m){
        int tk = -1,ans = INF;
        for(int i = 0; i <= 2; i++){
            if(ans > mat[m][statu^(1< mat[dep][dfs(dep+1,statu^(1<> ncase;
    tma[0] = "NNN",tma[1]="NNY",tma[2]="NYN",tma[3]="NYY",tma[4]="YNN",tma[5]="YNY",tma[6]="YYN",tma[7]="YYY";
    while(ncase--){
        cin >> m;
        memset(dp,-1,sizeof dp);
        for(int i = 1; i <= m; i++)
            for(int j = 0; j < 8; j++)
                cin >> mat[i][j];

        cout<

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved