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。
代码:
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
hdu3229
#include <cstdio>
#include <cstdlib>
#include <algorithm>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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]; // 用于剪枝,保存所有有意义按键
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int max(int x, int y)
{
if (x>y) return x;
else return y;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void Build_Confliction()
{
int K;
memset(conflict,0,sizeof(int)*128);
scanf("%d",&K);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (K--)
{
int t,i,conf = 0;
scanf("%d",&t);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=1; i<=64; i*=2)
{
conf += (t%10)*i; // 1100010 --> 98
t = t/10; //Track 1234567
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0; i<=127; i++)
{
conflict[conf|i] = 1;
}
}
return ;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void Build_Cut()
{
int t,k;
memset(total, 0, sizeof(int)*MAXN);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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]);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void init()
{
scanf("%d", &N);
memset(Track, 0, sizeof(int)*7*MAXN);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int i=0; i<=6; i++)
{
int C;
scanf("%d", &C);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (C--)
{
int t1,t2;
char t3;
scanf("%d%c", &t1, &t3);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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 ;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int solve()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (t=1; t<=N; t++)
{
for (j=0; j<=127; j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if ((j&total[t])==j)
{
int i, add_t = 0, pre = 0, now = 0, j_temp = j;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0; i<=6; i++)
{
if (Track[i][t] == 1 && ((1<<(6-i))&j) != 0)
add_t++; //是single note且按着
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (Track[i][t] == 3 && ((1<<(6-i))&j) != 0)
{
++add_t; //是strip note的起点且按着
now += (1<<(6-i));
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (Track[i][t] == 2 && ((1<<(6-i))&j) != 0)
{
now += (1<<(6-i)); //是strip note的中间,且上一秒按着,这一秒也按着,上一秒也必须按着
pre += (1<<(6-i));
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (Track[i][t] == 4 && ((1<<(6-i))&j) != 0)
{
++add_t; //是strip note的终点,这一秒暂时按着马上放掉,上一秒必须按着
pre += (1<<(6-i));
j_temp -= (1<<(6-i)); //放掉,避免出现不必要的冲突
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int T,Cases;
scanf("%d", &T);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (Cases = 1; Cases <= T; Cases++)
{
init();
printf("Case #%d: %d\n", Cases, solve());
}
//system("pause");
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)