水一些dp的联系题
标签： dp
hdu_2045
- 题意
一穿珠子，用三种颜色染色，要求相邻的珠子和两端的珠子不能是同一种颜色，求当有n个珠子的时候有几种染色方案
- 题解
表示dp[i][j][k] 表示开始位置为k当前i位置为j的最大值
- 代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
ll dp[55][3][3];//dp[i][j][k] 表示开始位置为k当前i位置为j的最大值
void init()
{
dp[0][0][0] = dp[0][1][1] = dp[0][2][2] = 1;
dp[0][1][0] = dp[0][2][0] = dp[0][0][1] = dp[0][2][1] = dp[0][0][2] = dp[0][1][2] = 0;
for(int i = 1; i < 55; i++){
dp[i][0][0] = dp[i-1][1][0] + dp[i-1][2][0];
dp[i][1][0] = dp[i-1][0][0] + dp[i-1][2][0];
dp[i][2][0] = dp[i-1][1][0] + dp[i-1][0][0];
dp[i][0][1] = dp[i-1][1][1] + dp[i-1][2][1];
dp[i][1][1] = dp[i-1][0][1] + dp[i-1][2][1];
dp[i][2][1] = dp[i-1][1][1] + dp[i-1][0][1];
dp[i][0][2] = dp[i-1][1][2] + dp[i-1][2][2];
dp[i][1][2] = dp[i-1][0][2] + dp[i-1][2][2];
dp[i][2][2] = dp[i-1][1][2] + dp[i-1][0][2];
}
}
int main()
{
init();
int n;
while(~scanf("%d",&n))
{
if(n==1)puts("3");
else
printf("%lld
",dp[n-1][1][0]+dp[n-1][2][0]+dp[n-1][0][1]+dp[n-1][2][1]+dp[n-1][1][2]+dp[n-1][0][2]);
}
return 0;
}
hdu_1297(大数+递推)
推荐一个对这个题讲解很好的博客：http://blog.sina.com.cn/s/blog_8a24b3a301010nwc.html
下面是这个博客的核心内容：
1.首先，n个人时，假设n个人的组合是合法的，这样的一个合法的组合设为(f(n))
2.为了保证n个人的时候是合法的，讨论一下第n个位置的人的性别
（1）如果第n个人是男性，那么前n-1个人，无论是什么样的组合，显然都是能保证n个人的组合是合法的，所以是(f(n-1))
（2）如果第n个是女性的话，那么第n-1个人的性别必须是女性，这样才能保证n个人的组合是合法的！
然后我们需要考虑前n-2个人在合法与不合法这两种情况下都能使n个人的组合都合法的问题 。
*如果前n-2个人的组合是合法的，那么这个组合为(f(n-2))
*如果前n-2的人的组合是不合法的话，那如果要满足当前的是合法的话，n-1位置一定是F，而且如果是非法的话前面n-2 = F ,n-3 = M 只有这一种情况是可行的。这种情况(f(n-4))就是合法的了。
所以得到的递推公式就是(f(n)=f(n-1)+f(n-2)+f(n-4))
下面是代码：
这里注意一下大数要用java
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
public static void main(String []args)
{
Scanner cin = new Scanner(System.in);
Integer N = 1001,i;
BigInteger[] f = new BigInteger[N];
f[1] = BigInteger.valueOf(1);
f[2] = BigInteger.valueOf(2);
f[3] = BigInteger.valueOf(4);
f[4] = BigInteger.valueOf(7);
for(i = 5; i < N; i++){
f[i] = f[i-1].add(f[i-2]).add(f[i-4]);
}
while(cin.hasNext())
{
i = cin.nextInt();
System.out.println(f[i]);
}
}
}
hdu_1159
- 题意
求最长公共子序列
- 题解
(dp[i][j])表示第一个字符串扫描到第i 个位置看，第二个字符串扫描到j个位置的最长公共子序列，那么有如果(s[i]=t[j])则满足(dp[i][j]=dp[i-1][j-1]+1),否则，有(dp[i][j] = max(dp[i-1][j],dp[i][j-1]))
注意两个细节：
1，字符串的编号最好从1开始，这样可以避免初始化字符长度为1的情况。
2，输入的时候数组如果从s+1的地方输入，则求数组长度的时候也要(len1 = strlen(s+1))
下面是代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 1008;
char s[N];
char t[N];
int dp[N][N];
int main()
{
while(cin>>(s+1)>>(t+1)){
int len1 = strlen(s+1);
int len2 = strlen(t+1);
memset(dp,0,sizeof(dp));
for(int i = 1; i <= len1; i++){
for(int j = 1; j <= len2; j++){
if(s[i]==t[j]) dp[i][j] = max(dp[i-1][j-1]+1,max(dp[i-1][j],dp[i][j-1]));
else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
printf("%d
",dp[len1][len2]);
}
return 0;
}
hdu_2563
题目很简单直接上代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[25][3];//dp[i][0]表示第i步向上走。。。
void init()
{
dp[0][1] = dp[0][0] = dp[0][2] = 1;
for(int i = 1; i < 25; i++){
dp[i][0] = dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
dp[i][1] = dp[i-1][0]+dp[i-1][1];
dp[i][2] = dp[i-1][0]+dp[i-1][2];
}
}
int main()
{
int T,n;
init();
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("%d
",dp[n-1][0]+dp[n-1][1]+dp[n-1][2]);
}
return 0;
}
hdu_2190
题解
dp[i][j]表示当前列有没有2*2的瓷砖
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int dp[35];
void init()
{
dp[0] = 1;
dp[1] = 3;
for(int i = 2; i < 35; i++){
dp[i] = dp[i-1]+2*dp[i-2];//dp[i][j]表示当前列有没有2*2的瓷砖
}
}
int main()
{
int T,n;
init();
scanf("%d",&T);
while(T--){
scanf("%d",&n);
printf("%d
",dp[n-1]);
}
return 0;
}
hdu_2041
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 50;
int dp[N];
void init()
{
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= N; i++){
dp[i] = dp[i-1]+dp[i-2];
}
}
int main()
{
init();
int T,m;
scanf("%d",&T);
while(T--){
scanf("%d",&m);
printf("%d
",dp[m]);
}
return 0;
}