HDU - 6806 Equal Sentences（dp）
传送门
挺容易看出来的dp，我们可以将问题简化为从第二个字符串开始，是否和前一个字符串交换位置，那么不难得出如下状态定义：
设 d [ i ] [ 0 / 1 ] d[i][0/1] d[i][0/1]表示到第 i i i个字符串和前一个交换/不交换的字符串排列个数，那么状态转移方程为：
- d [ i ] [ 0 ] = d [ i − 1 ] [ 0 ] + d [ i − 1 ] [ 1 ] d[i][0]=d[i-1][0]+d[i-1][1] d[i][0]=d[i−1][0]+d[i−1][1]
- d [ i ] [ 0 ] = ( s [ i ] = = s [ i − 1 ] ? 0 : d [ i − 1 ] [ 0 ] ) d[i][0]=(s[i]==s[i-1]?0:d[i-1][0]) d[i][0]=(s[i]==s[i−1]?0:d[i−1][0])
初始化为 d [ 1 ] [ 0 ] = 1 , d [ 1 ] [ 1 ] = 0 d[1][0]=1,d[1][1]=0 d[1][0]=1,d[1][1]=0，最终的答案即为 d [ n ] [ 0 ] + d [ n ] [ 1 ] d[n][0]+d[n][1] d[n][0]+d[n][1]
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=1e5+10;
ll d[maxn][2];
char s[maxn][12];
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s",s[i]);
d[1][0]=1,d[1][1]=0;
for(int i=2,x;i<=n;i++){
d[i][0]=(d[i-1][0]+d[i-1][1])%Mod;
if(strcmp(s[i],s[i-1])!=0)
d[i][1]=d[i-1][0];
else d[i][1]=0;
}
ll ans=(d[n][0]+d[n][1])%Mod;
printf("%lld\n",ans);
}
return 0;
}