题目描述
很多人都知道玩麻将，当然也有人不知道，呵呵，不要紧，我在这里简要地介绍一下麻将规则：
普通麻将有砣、索、万三种类型的牌，每种牌有1~9个数字，其中相同的牌每个有四张，例如1砣~9砣，1索~9索，1万~9万各有4张，所以共36*3=108张牌。胡牌时每人有14张牌，其中只要某人手里有若干句话（就是同种类型的牌连续三张或同种牌三张），另外再加上一对，即可胡牌。当然如果全是对，叫七小对，也可以胡牌。下图是连三张示例。
要判断某人是否胡牌，显然一个弱智的算法就行了，某中学信息学小组超级麻将迷想了想，决定将普通麻将改造成超级麻将。
所谓超级麻将没有了砣、索、万的区分，每种牌上的数字可以是1~100，而每种数字的牌各有100张。另外特别自由的是，玩牌的人手里想拿多少张牌都可以，好刺激哦！
刺激归刺激，但是拿多了怎么胡牌呢？
超级麻将规定只要一个人手里拿的牌是若干句话（三个连续数字的牌各一张组成一句话，三张或者四张同样数字的牌也算一句话），再加上一对相同的牌，就算胡了。
作为信息学竞赛选手的你，麻烦你给这位超级麻将迷编个程序，判断能否胡牌。
输入输出格式
输入格式：
输入文件第一行一个整数N（N<=100），表示玩了N次超级麻将。
接下来N行，每行100个数a1..a100，描述每次玩牌手中各种牌的数量。ai表示数字为i的牌有ai张。（0<=ai<=100）
输出格式：
输出N行，若胡了则输出Yes，否则输出No，注意区分Yes，No的大小写！
思路：
HXY大神据说0msA题，Orz
这道题我用了一种相当暴力的DP，卡过去了。。。
我们开一个DP数组：dp[i][j][k][0/1]
第一维表示在哪个位置，第二维表示前一个位置麻将还剩下几张，第三维表示现在位置还剩下几张，第四位表示当前是否走过对子
dp数组的值表示这种情况能不能到达
我们枚举位置，前一位要用掉多少，这一位要用掉多少，有没有用过对子
转移即可
代码：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define rii register int i #define rij register int j #define rik register int k #define rit register int t using namespace std; int n,x[105],dp[105][105][105][2]; int main() { // freopen("1.in","r",stdin); scanf("%d",&n); for(rit=1;t<=n;t++) { memset(dp,0,sizeof(dp)); for(rii=1;i<=100;i++) { scanf("%d",&x[i]); } dp[0][0][0][0]=1; for(rii=1;i<=100;i++) { for(rij=0;j<=x[i-1];j++) { for(rik=0;k<=x[i];k++) { if(k>1) { dp[i][j][k][1]|=dp[i][j][k-2][0]; } if(k>2) { dp[i][j][k][1]|=dp[i][j][k-3][1]; dp[i][j][k][0]|=dp[i][j][k-3][0]; } if(k>3) { dp[i][j][k][1]|=dp[i][j][k-4][1]; dp[i][j][k][0]|=dp[i][j][k-4][0]; } if(i-2<0&&k==0&&j>k) { dp[i][j][k][0]|=dp[i-1][0][j-k][0]; dp[i][j][k][1]|=dp[i-1][0][j-k][1]; } if(j>=k&&x[i-2]>=k) { dp[i][j][k][0]|=dp[i-1][x[i-2]-k][j-k][0]; dp[i][j][k][1]|=dp[i-1][x[i-2]-k][j-k][1]; } } } } if(dp[100][x[99]][x[100]][1]==1) { cout<<"Yes"<<endl; } else { cout<<"No"<<endl; } } }