题目：https://www.luogu.org/problemnew/show/P2593
发现三个连续牌的影响范围只有3、相同牌的影响范围只有1之后就可以dp了。
O(100^7)T飞。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int T,a[N];
bool dp[][N][N][N],flag;
int rdn()
{
int ret=;char ch=getchar();
while(ch>''||ch<'')ch=getchar();
while(ch>=''&&ch<='')(ret*=)+=ch-'',ch=getchar();
return ret;
}
int main()
{
T=rdn();
while(T--)
{
for(int i=;i<=;i++)a[i]=rdn();
for(int t=;t<=;t++)if(a[t]>=)
{
a[t]-=;
memset(dp[],,sizeof dp[]);
dp[][a[]][a[]][a[]]=;
for(int i=;i<=;i++)
{
flag=;int d=(i&);
memset(dp[!d],,sizeof dp[!d]);
for(int x=;x<=a[i-];x++)
for(int y=;y<=a[i-];y++)
for(int z=;z<=a[i];z++)
if(dp[d][x][y][z])
{
int lm=min(x,min(y,z));
for(int k=;k<=lm;k++)
{
dp[!d][y-k][z-k][a[i+]]|=(((x-k)%==)|((x-k)%==));
if(dp[!d][y-k][z-k][a[i+]])flag=;
}
}
if(!flag)break;
}
a[t]+=;
if(flag)break;
}
if(flag)printf("Yes\n");else printf("No\n");
}
return ;
}
如果不枚举对子在哪而是带一个0/1在状态里的话可以少乘一个100。
如果不无脑记录前两个位置而是仅记录前一个位置、用三连的时候调用一下上一层的话可以少乘一个100。
这是因为最后要的只有dp[ ][0][0][0]，所以保存很多“之前位置还不是0”的状态比较浪费。
不枚举用了几个三连，而是每层用“从开头降到这里”更新一下本层，就能把”在本层用较少的三连“包括在“用单个位置从之前层降下来”。这样可以少乘一个100。
这里调了好久！必须是“从开头降到这里”，而不能是“从这里降到0”；因为从“这里”降的话需要判断本层是否可行，但这个可行是包括 i-2 的状态的，自己仅记录前一个位置的dp不能存下。如果是”从开头降到这里“的话，本层目前一定是可行的。
O(100^4)卡过。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int T,a[N];
bool dp[N][N][N][];
int rdn()
{
int ret=;char ch=getchar();
while(ch>''||ch<'')ch=getchar();
while(ch>=''&&ch<='')(ret*=)+=ch-'',ch=getchar();
return ret;
}
int main()
{
T=rdn();
while(T--)
{
memset(dp,,sizeof dp);
for(int i=;i<=;i++)a[i]=rdn();
dp[][][a[]][]=;
for(int i=;i<=;i++)
{
for(int x=a[i-];x>=;x--)
for(int y=a[i];y>=;y--)
{
dp[i][x][y][]|=dp[i][x][y+][]; dp[i][x][y][]|=dp[i][x][y+][];
dp[i][x][y][]|=dp[i][x][y+][]; dp[i][x][y][]|=dp[i][x][y+][];
dp[i][x][y][]|=dp[i][x][y+][];
//在a[i]变成各种y之后尝试一下从开头降到这里(先降后单个弄)
dp[i][x][y][]|=dp[i-][a[i]-y][x+a[i]-y][];
dp[i][x][y][]|=dp[i-][a[i]-y][x+a[i]-y][]; //在a[i]变成各种y之后尝试一下取完
// dp[i][x][0][0]|=dp[i-1][y][x+y][0];//不能&dp[i][x+y][y],因含义是i-2==0
// dp[i][x][0][1]|=dp[i-1][y][x+y][1];//不&的话会出错：0 3 0(原为2)
//因为从当前降到0的话，需要判断当前是否可行
//可是降还需要i-2的也许有值，与表示“当前可行”的dp冲突，即无法表示当前是否可行
//而“从开头”降的话，一定可行 //x之所以不是0，是因为这里用到dp[i-1][y][][]
if(!x)
{
dp[i+][y][a[i+]][]|=dp[i][][y][];
dp[i+][y][a[i+]][]|=dp[i][][y][];
}
// if(i<=3)
// {
// if(dp[i][x][y][0])printf("dp[%d][%d][%d][%d]=%d\n",i,x,y,0,dp[i][x][y][0]);
// if(dp[i][x][y][1])printf("dp[%d][%d][%d][%d]=%d\n",i,x,y,1,dp[i][x][y][1]);
// }
}
}
puts(dp[][][][]?"Yes":"No");
}
return ;
}