首页 > ACM题库 > HDU-杭电 > HDU 3229-Jinyuetuan Puzzle[解题报告]HOJ
2014
03-09

HDU 3229-Jinyuetuan Puzzle[解题报告]HOJ

Jinyuetuan Puzzle

问题描述 :

Island Explorer

JinYueTuan is a famous online game which has been in vogue for a long time. Large number of players put themselves in it day after days…

JinYueTuan is a simple game with these rules:
Only seven keys on the keyboard will be used in games, each key are assigned to one of the seven sound tracks. During the game, a series of notes may fall in each sound track irregularly. When notes fall down in one sound track, player should press the assigned key at once. If so, then got a “Cool”, or get “Miss” otherwise.

There are two types of “Note”: “single note” and “strip note”. Just as the name implies, “single note” means a single note, press right key at the right time once, then you can get a “Cool”, otherwise “Miss”; “strip note” needs you keeping press the corresponding key from the start time to the end time of the note. Press key at the begin time you may get a “Cool”, and release at the end time to get another “Cool”, you will “Miss” either early or late. If “Miss” at the begin time, then “Miss” the other (the end time) immediately.

People lament about the fact that such an easy game is limited by the hardware design, the so-called “keys confliction”. “keys confliction” means some key combinations cannot be pressed. For example, when Track 1,4,5,6 fall a note at the same time respectively, we should press the four keys at the same time, but now, keys confliction may happen, and cause this to fail, then you will “Miss” all these four notes. Keys confliction meets the relation of inclusion, in other words, if keys set S would cause the confliction, so would keys set T when S is included in T. Note that, if at a certain moment in time, some keys should be pressed and some pressing keys should be released, then you can release and press at the same time, and released keys won’t cause any keys confliction at all.

Because of the keys confliction, we have to give up some notes to save as more other notes as possible. More details will be explained in the sample data.

Now you know the falling time and type (single or strip) of each note in each sound track, and all keys-assembling that may cause confliction. Your task is to calculate the maximum number of “Cool” that player can get.

输入:

There are multiple test cases, the number of them T is given in the very first line, followed by T cases.

For each test case:
First line contains an integer N, the length of the music (1≤N≤1000).
The next 7 lines will contain description of each sound track. The first number in each line, C, denote the number of notes in that sound track. Following C description of each note: A single number “A” denotes an single note at Time A(1≤A≤N); A pair of integers separating by ‘-’,”A-B” denotes a strip note start at Time A and end at Time B(1≤A<B≤N). In each sound track, no superposition exists, no strip starts at another’s end time, no single notes puts in a strip(includes begin and end point).

The next line contain a single integer K (0≤K<27), denotes K descriptions of Keys Confliction are following.

Each description is a single line containing a string of seven characters S0 S1 S2…S6, if Sk1,Sk2,…,Sks were character ‘1’ and others were ‘0’, that means key combination Sk1Sk2…Sks may cause Keys Confliction.

输出:

There are multiple test cases, the number of them T is given in the very first line, followed by T cases.

For each test case:
First line contains an integer N, the length of the music (1≤N≤1000).
The next 7 lines will contain description of each sound track. The first number in each line, C, denote the number of notes in that sound track. Following C description of each note: A single number “A” denotes an single note at Time A(1≤A≤N); A pair of integers separating by ‘-’,”A-B” denotes a strip note start at Time A and end at Time B(1≤A<B≤N). In each sound track, no superposition exists, no strip starts at another’s end time, no single notes puts in a strip(includes begin and end point).

The next line contain a single integer K (0≤K<27), denotes K descriptions of Keys Confliction are following.

Each description is a single line containing a string of seven characters S0 S1 S2…S6, if Sk1,Sk2,…,Sks were character ‘1’ and others were ‘0’, that means key combination Sk1Sk2…Sks may cause Keys Confliction.

样例输入:

3
6
3 1 3 4
2 1 2-5
2 3 6
0
0
0
0
1
1110000
6
3 1 3 5
2 1 2-5
2 5 6
0
0
0
0
1
1110000
6
1 1
1 1-3
1 1
0
0
0
0
1
1110000

样例输出:

Case #1: 7
Case #2: 8
Case #3: 3

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

#define CL(a, b) memset(a, b, sizeof(a))
#define CLQ(q) while(!q.empty()) q.pop()
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define FS(i,s) for(int i=0;s[i];++i)
#define FD(i,a,b) for(int i=a;i>=b;--i)
#define FOREACH(itr,c) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define PR2(a,n,m) for(int i=0;i<n;++i){for(int j=0;j<m;++j)cout<<a[i][j]<<" ";puts("");}
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define checkMax(a,b) {if(a<b)a=b;}
#define checkMin(a,b) {if(a>b)a=b;}
#define sqr(x) ((x)*(x))
#define INF 100000000
#define EPS 1e-8
typedef long long LL;
const double pi = acos(-1.0);
#define PII pair<int,int>
#define MP make_pair
#define db double
//-----------------------------------------------------------
#define N 1005

const int M = (1<<7);
int a[N][7],sta[N];
int f[N][M];
int sub[M][M],si[M];
int n,tot;
bool o[M];

void getdata(void);
void initsub(void);

int main() {
#ifndef ONLINE_JUDGE
 freopen("in", "r", stdin);
// freopen("out", "w", stdout);
#endif
 int t,ca,ans;
 int i,j,k,l,tj,tp,nx,v,tp0;
 bool can;
 initsub();
 cin >> t;
 for (ca=1;ca<=t;ca++)
 {
 getdata();
 CL(f,0);
 for (i=1;i<=n;i++)
 {
 tp0=sta[i-1];
 for (tj=0;tj<si[tp0];tj++)
 {
 j=sub[tp0][tj];
 tp=sta[i];
 for (k=0;k<si[tp];k++)
 {
 nx=sub[tp][k];
 if (o[j] && o[nx])
 {
 v=0;
 can=true;
 for (l=0;l<7;l++)
 {
 if (a[i][l]==-1 && (j&(1<<l)) && (nx&(1<<l))==0)
 v++;
 else if (a[i][l]==1 && (nx&(1<<l)))
 v++;
 else if (a[i][l]==2 && (nx&(1<<l)) && (j&(1<<l))==0)
 can=false;
 }
 if (can && f[i-1][j]+v>f[i][nx])
 {
 f[i][nx]=f[i-1][j]+v;
 //if (i==3 && nx==5) printf("f[%d][%d]+%d=f[%d][%d]=%d\n",i-1,j,v,i,nx,f[i][nx]);
 }
 }
 }
 //printf("f[%d][%d]=%d\n",i,k,f[i][k]);
 }
 }
 //printf("f[%d][%d]=%d\n",3,6,f[3][6]);
 ans=0;
 for (i=0;i<M;i++)
 if (o[i] && f[n][i]>ans)
 ans=f[n][i];
 printf("Case #%d: %d\n",ca,ans);
 }
 return 0;
}

void getdata(void)
{
 char ch,str[10];
 int i,j,k,m,s,t,v;
 scanf("%d",&n);
 CL(a,0);
 for (i=0;i<7;i++)
 {
 scanf("%d",&m);
 for (j=0;j<m;j++)
 {
 scanf("%d",&s);
 ch=getchar();
 if (ch=='-')
 {
 scanf("%d",&t);
 a[s][i]=1;
 for (k=s+1;k<t;k++)
 a[k][i]=2;
 a[t][i]=-1;
 }
 else
 a[s][i]=1;
 }
 }
 CL(sta,0);
 for (i=1;i<=n;i++)
 {
 for (j=0;j<7;j++)
 if (a[i][j]>0)
 sta[i]|=(1<<j);
 }
 CL(o,true);
 scanf("%d",&tot);
 for (i=0;i<tot;i++)
 {
 scanf(" %s",str);
 v=0;
 for (j=0;j<7;j++)
 if (str[j]=='1')
 v+=(1<<j);
 for (j=0;j<M;j++)
 if ((j|v)==j)
 o[j]=false;
 }
}

void initsub(void)
{
 int i,j;
 for (i=0;i<M;i++)
 {
 si[i]=0;
 for (j=0;j<=i;j++)
 if ((i|j)==i)
 sub[i][si[i]++]=j;
 }
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。