本文主要是介绍vijos 1193 dp,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
每一行的状态由之前两行决定,dp[i][t][k]表示第i行状态为k,下一行状态为t时的种数,然后dp一遍即可。
代码:
#include <iostream>
#include <cstring>
#include <cstdio>using namespace std;int a[10010];
int dp[10010][2][2]; //1下一行还需要一个1,0下一行不需要1int main()
{int n;scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]);memset(dp,0,sizeof(dp));dp[0][0][0]=1;dp[0][1][0]=1;for (int i=1;i<=n;i++){if (a[i]==0){dp[i][0][0]=dp[i-1][0][0];}else if (a[i]==1){dp[i][1][0]=dp[i-1][0][0];dp[i][0][1]=dp[i-1][1][0];dp[i][0][0]=dp[i-1][0][1];}else if (a[i]==2){dp[i][0][1]=dp[i-1][1][1];dp[i][1][0]=dp[i-1][0][1];dp[i][1][1]=dp[i-1][1][0];}else if (a[i]==3){dp[i][1][1]=dp[i-1][1][1];}}printf("%d\n",dp[n][0][0]+dp[n][0][1]);
}
这篇关于vijos 1193 dp的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!