dango

Hdu3229 Jinyuetuan Puzzle

题目大意：

    原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=3229

    劲乐团游戏，得分种类：

1、  single note，按一下键得一个cool

2、  strip note，开始时按一下键得一个cool，结束时放开再得一个cool。若开始时miss或者中途放开按键，都不可以得到结束的cool。

键盘有一些冲突按键，如“1110000”代表前三个按键不可以同时按下，包括冲突按键的所有按键组合都会miss那一秒的所有note，例如“1110000”是冲突按键，“1110001”也会产生冲突。

题目分析：

    首先很容易想到这是一个动态规划问题，阶段是时间，状态是不同的按键状态。即可以用f[t][state]来表示第t秒结束后，按键状态为state时可以得到的分数。

    但是一些适当的优化是必要的，否则N*state*state*7，也就是1000*128*128*7加上多组测试数据，只要数据不是太水肯定会超过时限。

    动归方程：F[t][now] = max(add_cool + f[t-1][k], f[t][now])

    其中now是这一时刻按死的按键，pre是上一时刻必须按死的按键，k是所有包含pre的有效按键。

    下面是一些优化细节：

1、  首先先对所有按键状态做一次预处理，用conflict[state]表示state这个按键组合是否会产生冲突，这样动归的时候可以方便判断是否产生冲突。

2、  预处理每一秒所有得分按键的组合total[t]，当动态规划到时间t的时候，若枚举的按键state不包含在total[t]内也直接忽略过去（这个预处理去掉就TLE了……）

3、  时间t，枚举每个按键的时候，即处理f[t][state]时，在考察这么按可以增加多少个cool的同时：处理一下如此按键上一秒的必须按键，即哪一些键在上一秒必须按死，记为pre；处理一下这一时刻必须按死的键，记为now。因为作为single note的得分按键，对上一秒下一秒都没有影响，在不冲突的情况下得到cool就可以了。进而在枚举f[t][state]的前一秒按键k的时候，k显然必须包含pre，避免再进行判断之类。

在strip note这里其实还有一些细节需要处理。这一个细节导致了我的一次Wrong Answer。在枚举按键的时候，不妨应该将strip note的终点也暂时记为按下，但是不参与冲突按键的判断。否则枚举f[t][state]中的state时候，若strip note是放开的，无法判断是不要得分的放开，还是得分的放开。

小结：

    动态规划除了需要事先有一个严密的转移方程，像这种比较麻烦的题目许多细节也需要考虑进去。

    面对看似恐怖的时间复杂度（尤其是徘徊在TLE边缘的时间复杂度）不要退缩，有的时候一个小小的优化，譬如上述中total[t]的预处理就可以把程序从TLE带向AC。

代码：

hdu3229
#include <cstdio>
#include <cstdlib>
#include <algorithm>

const int MAXN = 1000 + 10;
const int INF = 1<<29;
 
int N, Track[7][MAXN],conflict[128];     //Track[i][j] = 1 single
                                        //Track[i][j] = 2 (3 start 4 end)
                                        //Track[i][j] = 0 nothing 
int total[MAXN];                        // 用于剪枝，保存所有有意义按键 
int max(int x, int y){
    if (x>y) return x;
    else return y;
}

void Build_Confliction(){
    int K;
    memset(conflict,0,sizeof(int)*128);
    scanf("%d",&K);
    while (K--){
        int t,i,conf = 0;
        scanf("%d",&t);
        for (i=1; i<=64; i*=2){
            conf += (t%10)*i;                //        1100010 --> 98
            t = t/10;                        //Track 1234567
        }
        for (i=0; i<=127; i++){
            conflict[conf|i] = 1;
        }
    }
    return ;
}

void Build_Cut(){
    int t,k;
    memset(total, 0, sizeof(int)*MAXN);
    for (t=1; t<=N; t++){
        for (k=0; k<=6; k++)
            if (Track[k][t]>0)  
                total[t] |= (1<<(6-k));
        //printf("t = %d , total[t] = %d\n", t, total[t]);
    }
}

void init(){
    scanf("%d", &N);
    memset(Track, 0, sizeof(int)*7*MAXN);
    for (int i=0; i<=6; i++){
        int C;
        scanf("%d", &C);
        while (C--){
            int t1,t2;
            char t3;
            scanf("%d%c", &t1, &t3);
            if (t3=='-'){
                scanf("%d", &t2);
                Track[i][t1] = 3; Track[i][t2] = 4;
                for (int j=t1+1; j<t2; j++)
                    Track[i][j] = 2;
            }
            else
                Track[i][t1] = 1;
        }
    }
    Build_Confliction();
    Build_Cut();
    return ;
}

int solve()
{
    int f[MAXN][128],j,k,t,ans = 0;;
    for (t=0; t<=N; t++)
        for (j=0; j<=127; j++)
            f[t][j] = -INF;
    f[0][0] = 0;
    for (t=1; t<=N; t++){
        for (j=0; j<=127; j++)
            if ((j&total[t])==j){    
                int i, add_t = 0, pre = 0, now = 0, j_temp = j;
                for (i=0; i<=6; i++){
                    if (Track[i][t] == 1 && ((1<<(6-i))&j) != 0)
                        add_t++;                    //是single note且按着 
                    if (Track[i][t] == 3 && ((1<<(6-i))&j) != 0){
                        ++add_t;                    //是strip note的起点且按着 
                        now += (1<<(6-i));
                    }
                    if (Track[i][t] == 2 && ((1<<(6-i))&j) != 0){
                        now += (1<<(6-i));            //是strip note的中间，且上一秒按着，这一秒也按着，上一秒也必须按着
                        pre += (1<<(6-i));
                    }
                    if (Track[i][t] == 4 && ((1<<(6-i))&j) != 0){
                        ++add_t;                    //是strip note的终点，这一秒暂时按着马上放掉，上一秒必须按着 
                        pre += (1<<(6-i));
                        j_temp -= (1<<(6-i));        //放掉，避免出现不必要的冲突 
                    }
                }
                if (!conflict[j_temp]){ 
                    for (k=0; k<=127; k++)
                        if (!conflict[k] && ((pre&k)==pre) && f[t-1][k] != -INF)
                            f[t][now] = max(add_t + f[t-1][k], f[t][now]);
                }
            }
    }
    for (j=0; j<=127; j++)
        if (f[N][j]>ans) ans = f[N][j];
    return ans;
}

int main(){
    int T,Cases;
    scanf("%d", &T);
    for (Cases = 1; Cases <= T; Cases++){
        init();
        printf("Case #%d: %d\n", Cases, solve());
    }
    //system("pause");
    return 0;
}