动态规划专题
背诵圆周率
题意
背诵圆周率时可以将圆周率数字划分不同的组降低难度，下面有4个分类情况，每个分类有不同的难度，将圆周率划分完后将难度加在一起就是此时的难度，要求给定长度为n的数字后，每次划分3个到5个数字，求划分后的最小难度
所有数字相同 333 555 难度 1
数字逐个递减 23456 难度 2
两个数字交替出现 323 4545 难度 4
等差数列 147 难度 5
其他 情况 17912 331 难度 10
测试
输入 1 2 3 4 1 2 3 4
输出 2
#include<iostream>
#include<vector>
#include<algorithm>
#define N 100
using namespace std;
int cae[N];
vector<int> pi;
int classfiy(int start,int l)
{
if (l == 3)
{
if (pi[start] == pi[start + 1] && pi[start] == pi[start + 2])
{
return 1;
}
if (pi[start + 1] == pi[start] + 1 && pi[start + 2] == pi[start + 1] + 1)
{
return 2;
}
if (pi[start] == pi[start + 2])
{
return 4;
}
if (pi[start + 1] - pi[start] == pi[start + 2] - pi[start + 1])
{
return 5;
}
return 10;
}
if (l == 4)
{
if (pi[start] == pi[start + 1] && pi[start] == pi[start + 2]&&pi[start]==pi[start+3])
{
return 1;
}
if (pi[start + 1] == pi[start] + 1 && pi[start + 2] == pi[start + 1] + 1&&pi[start+3]==pi[start+2]+1)
{
return 2;
}
if (pi[start] == pi[start + 2]&&pi[start+1]==pi[start+3])
{
return 4;
}
int res = 0;
res = pi[start + 1] - pi[start];
if (res == pi[start + 2] - pi[start + 1] && pi[start + 3] - pi[start + 2] == res)
{
return 5;
}
return 10;
}
if (l == 5)
{
if (pi[start] == pi[start + 1] && pi[start] == pi[start + 2] && pi[start] == pi[start + 3]&&pi[start]==pi[start+4])
{
return 1;
}
if (pi[start + 1] == pi[start] + 1 && pi[start + 2] == pi[start + 1] + 1 && pi[start + 3] == pi[start + 2] + 1&&pi[start+4]==pi[start+3]+1)
{
return 2;
}
if (pi[start] == pi[start + 2] && pi[start + 1] == pi[start + 3]&&pi[start]==pi[start+4])
{
return 4;
}
int res = 0;
res = pi[start + 1] - pi[start];
if (res == pi[start + 2] - pi[start + 1]&&pi[start+3]-pi[start+2]==res&&pi[start+4]-pi[start+3]==res)
{
return 5;
}
return 10;
}
}
int minhard(int start)
{
int& ret = cae[start];
if (ret != 100)
{
return ret;
}
int l = 3;
for (; l < 6; l++)
{
if (start + l < pi.size()+1)
{
ret = min(ret, classfiy(start, l) + minhard(start + l));
}
if(start==pi.size())
{
return 0;//当最后不能够继续划分时直接返回难度10，作为初始部分，就不在上面的函数中处理。
}
else if(start+l>pi.size())
{
return ret=min(ret, 10);
}
}
return ret;
}
int main()
{
int i = 0;
int a = 0;
cout << "输入数字输入-1结束以空格为间隔：" << endl;
cin >> a;
while (a!=-1)
{
pi.push_back(a);
cin >> a;
}
for (i = 0; i < 10; i++)
{
cae[i] = 100;
}
int res = 0;
res = minhard(0);
cout << endl << "最小难度为:" << res << endl;
}
铺设方法个数
用21大小的瓷砖铺盖2n大小的长方形，共有多少种方法。
分析
这道题关键在于问题的转化，2width的白板，每次盖
21的板，每次盖上一块板时，无论是横盖还是竖盖，都会使
整个板的长width，减少一或或2，并且，无论你前一次如何盖板，
不会影响到后一次的盖板的方法数，所以问题可以转化为：
til(n)=当长度为n时能盖板的方法
til(n)=til(n-1)+til(n-2);
处理好初始部分和递归关系就OK。
#include<iostream>
using namespace std;
#define M 10000000
int n;
int cae[10];//用二维数组表示要盖的板，盖住为1，没盖住为0
int til(int width)
{
// 对于2*1 的话可以有两种方法。
if(width <=1)return 1;
int& ret = cae[width];
if (ret != 0)
{
return ret;
}
ret = til(width - 1) + til(width - 2);
return ret;
}
int main()
{
cout << "请输入板的长度" << endl;
cin >> n;
int res = 0;
res = til(n);
cout << "方法有：" <<res <<endl;
}
非对称铺设方法个数
间接求法，用总的减去对称的个数，计算对称的，可以将n分为奇数与偶数两种情况。
int asymmetric(int width){
if(width %2 == 1)
return (tiling(width)-tiling(width/2)+ MOD)%MOD;
int ret = tiling(width);
ret = (ret - tiling(width/2) + MOD) % MOD;
ret = (ret - tiling(World/2 - 1)+ MOD) % MOD;
return ret;
}
爬出水井的蜗牛
一只蜗牛在深度为n米的井里，蜗牛想爬出去，由于天气原因每次只能爬1米或者2米，每天是阴天和晴天的概率各为50%，问蜗牛能否在m天内爬出。
分析
定义climd(day,climbed)=蜗牛在day天爬行了climbed米时能够在mt天内爬行n米的个数，所以
climb(day,climbed)=climb(day+1,climbed+1)+climb(day+1,climbed+2);
测试
输入 n 10
m 7
输出 99
代码：
#include<iostream>
using namespace std;
int cae[100][100];
int m;
int n;
int climb(int day, int climbed)
{
if(days == m)return climbed>=n?1:0;
int& ret = cae[day][climbed];
if (ret != 0)return ret;
// 每一天的下一天，要么是晴天，要么是阴天。两种状态。
return ret = climb(day + 1, climbed + 1) + climb(day + 1, climbed + 2);
}
int main()
{
cout << "请输入水井高度" << endl;
cin >> n;
cout << "请输入天数" << endl;
cin >> m;
int res = climb(0, 0);
cout << res << endl;
}
多联骨牌
纵向单调多联骨牌
题意：
以n个正方形形成多联骨牌时，计算纵向单调多联骨牌的个数。
代码：
const int MOD = 10*1000*1000;
int cache[101][101];
//以n个正方形组成，返回第一行包含first个正方形的
//多联骨牌的个数
int poly(int n,int first){
//初始部分：n == first
if(n == first) return 1;
//制表
int &ret = cache[n][first];
if(ret != -1)return ret;
ret = 0;
for(int second = 1;second<= n-first;++second){ // second 是第二行的正方形个数
int add = second + first -1; //连接方式的数量
add *= poly(n-first,second);
add %= MOD;
ret += add;
ret %= MOD;
}
return ret;
}
逃狱的汉尼拔博士
题干：
杀人狂魔汉尼拔博士逃狱了。通缉令发布后，大量军警出动并实施全天候追捕，不过狡猾的汉尼拔博士并没有落网。过了d日后，束手无策的警察们拜访了有着“编程天才”之称的查理教授。查理教授对汉尼拔博士留在监狱的笔记本进行分析后，做出了如下假设。
）汉尼拔博士为了避开检查，只走山路；
）汉尼拔博士越狱当天选择了与监狱相邻的村子之一作为藏身之处；
）汉尼拔博士为了逃避追捕，每天往一个相邻的村子逃窜。
为了验证假设，教授找到了与监狱所在村子以山路连接的n个村子的地图。汉尼拔博士会按照此假设行动，而且会随机选择一个备选的村子。编写程序计算d日后汉尼拔博士在各个村子的概率。
例如监狱在第三个村子，逃狱后的汉尼拔博士会在0、1、2、4、5中任意选择一个村子藏身。因此，1天后汉尼拔博士藏在第0号村子的概率是1/5，两天后藏在第1号村子的概率是1/15。
输入：
第一行输入测试用例的个数C（1≤C≤50）。之后各行输入地图上显示的村子个数 N（2≤N≤50）和逃狱后经过的天数D（1≤D≤100），以及监狱所在村子的号码P（0≤P<N），村子的号码由0到N-1的数字组成。之后N行里各输入N个整数，形成一个序列A。第i行j列的数值A[i][j]如果等于1，就表示从第i号村子到第j号村子有山路可走；如果是0，则表示无路可通。接下来的一行输入要计算概率的村子的个数T（0≤T<N），最后一行以整数型输入要计算概率的村子的号码Q（0≤Q<N）。
如果一个村子与另一个村子相连，那么相反的路径也必定存在。可假设一个村子连接到自身的路径不存在。
输出：
每个测试用例以T个实数输出汉尼拔博士可能藏匿的概率。存在小于10-7的绝对/相对误差的答案将被视为正确答案。
示例输入值：
2
5 2 0
0 1 1 1 0
1 0 0 0 1
1 0 0 0 0
1 0 0 0 0
0 1 0 0 0
3
0 2 4
8 2 3
0 1 1 1 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 0 0 0 0
1 1 1 0 1 1 0 0
0 0 0 1 0 0 1 1
0 0 0 1 0 0 0 1
0 0 0 0 1 0 0 0
0 0 0 0 1 1 0 0
4
3 1 2 6
示例输出值：
0.83333333 0.00000000 0.16666667
0.43333333 0.06666667 0.06666667 0.06666667
代码：
int n,d,p,q; // 监狱p，终点q
//cache 初始化为-1
double cache[51][101];
//connect[i][j] 表示i村与j村是否相连
//deg[i] = 与i村相连的村庄的数量
int connect[51][51],deg[51];
//假设在第days天躲藏在here号村子
//则返回最后一天躲藏在第q号村的条件概率
double search(int here,int days){
//初始部分：已过d天的情况
if(days == d)return (here == q?1.0:0.0); //是否是要到的点
//制表
double &ret = cache[here][days];
if(ret >-0.5)return ret;
ret = 0.0;
for(int there = 0;there<n;++there){
if(connect[here][there])
ret += search(there,days+1)/deg[here]; //连接的边数
}
return ret;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献4条内容
所有评论(0)