QU66Q
- 浏览: 66216 次
- 性别:
- 来自: 北京
-
最新评论
文章列表
题目大意：
给定一个字符串，用最少的插入操作的次数，使得该字符串变为回文。
解题思路：
和UVA（10739） String to Palindrome一样，求出最少的操作次数，唯一不一样的就是这道题要将还原的回文输出出来。
设置 dp[i][j] 表示第 i 个字符到第 j 个字符是回文时所需要操作的最少次数，字符串为 s ， 则状态转移方程为：
if( s[i] == s[j] )
dp[i][j] = dp[i+1][j-1];
else
dp[i][j] = min( dp[i+1][j], dp[i][ ...
题目大意：
在10000以内的正整数中，有些数可以开3次方，给定一个正整数，可以由一些能够开3次方的数组成，求出共有几种组成方式。
解题思路：
该题和硬币找零的题目相似，可以参考UVA Dollars(147)。先算出所有能够开3次方的数，这些数相当于可以用的硬币，后面的求法就和UVA Dollars(147)一样了。状态转移方程为：
dp[n] += dp[n-v[m]];
其中，dp[n] 表示组成 n 有几种方法，v[m] 存储所有能够开3次方的数。
代码：
#include <iostream>
#includ ...
题目大意：
给定一个字符串，问在该字符串的所有子串中，有多少个是回文？
解题思路：
动态规划，设定 dp[i][j] 表示第 i 个字符到第 j 个字符里是回文的个数，设字符串为 s，则状态转移方程为：
（1）s[i] == s[j]
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + dp[i+1][j-1] + 1;
当s[i] == s[j]时，要考虑s[i+1]到s[j]的回文数加上s[i] 到s[j-1]的回文数，由于两者都算的s[i+1]到s[j-1]的回 ...
UVA Chopsticks(10271)
- 博客分类：
- 动态规划
题目大意：
有N个数，每个数表示筷子的长度，要你选出n+8组三元组，即n+8组筷子，每组3支筷子，要求这三支筷子的长度满足x<=y<=z，其中代价为(x-y)^2。问最小的代价是多少。
解题思路：
动态规划问题，令dp[i][j] 表示从前 j 个数中选出 i 组三元组所需要的代价，则状态转方程为：
dp[i][j] = min( dp[i][j-1], dp[i-1][j-2] + badness[j] );
其中badness[j] 表示选择第 j 个数和第 j-1 ...
题目大意：
给你n个点以及每个点的搜索频率，构建一个最优二叉树，使得二叉树的总权重最小，总权重等于每个点的搜索频率乘以其相应的深度的总和。设有3个点e1, e2, e3， 其搜索频率为f(e1), f(e2), f(e3)， 若构建的二叉树中，其三个点在树中的深度分别为h1, h2, h3，则 W = f(e1) * h1 + f(e2) * h2 + f(e3) * h3。问题就是要求出最小的W。有点类似哈弗曼编码。
解题思路：
动态规划，每次状态都假设只有三个点，即根节点，左子树和右子树，遍历计算出每个节点作为根节点时的最小权重。
...
题目大意：
给定一个字符串，使用替换字符，增加字符和删除字符三种操作使得字符串变成回文，求出最少的操作次数。
解题思路：
动态规划题目，题中的增加字符和删除字符的操作本质上是一样的，可以都理解为增加字符。
设dp[i][j] 表示字符串第 i 个字符到第 j 个字符是回文所需操作的次数，则假设第 i+1 到 j-1 的字符是回文了，那么第 i 个字符和第 j 个字符就有两种情况，一种是相等，则 dp[i][j] = dp[i+1][j-1]， 即不用操作；另外一种是不相等，那么就得增加一次操作，操作的方式有三种： dp[i+1][j ...
CC2530芯片的IEEE Mac地址
- 博客分类：
- Zigbee
2.4G的CC253X芯片由TI公司生产，可以很容易建立在基于IEEE802.15.4标准协议上面，现今多数Zigbee传感节点都是用CC253X的芯片。
CC253X的IEEE地址共分为三种：Primary IEEE， Secondary IEEE和Random IEEE。其中Primary IEEE地址在生产时已经由TI预先确定，无法更改，而对于Secondary IEEE地址用户则可以更改，如果无法获取Primary IEEE 和 Secondary IEEE时，则会是用第三种随机地址来代替自己的Mac地址。
（1）Primary IEEE
...
题目大意：
有N个立方体，立方体的6个面颜色不一，现在要求立方体按照体重从小到大叠起来，并且两个立方体接触面的颜色必须相同，求最高能叠多高？
解题思路：
动态规划，本质上就是求最长递增子序列，同时加上了限制条件，就是两个立方体之间颜色要一样，所以我就先用动态规划求出最长符合要求的子序列的长度，同时记录序列最后一个元素的位置，然后再用递归输出子序列。求最长递增子序列的状态转移方程就不写了，直接看代码里面就有，就那么一行，主要就是在状态转移的时候加上判断条件，判断颜色是否一样，然后记录子序列最后一个元素用来递归用。递归的时候也一样，先要判断颜色。
代 ...
C++ 大数运算模板
- 博客分类：
- C++
该模板可以算加，减，乘，除基本运算，其中加法只能是大数减小数。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 1000;
struct bign
{
int len;
int s[maxn];
bign()
...
UVA Bachet's Game(10404)
- 博客分类：
- 动态规划
题目大意：
Stan和Ollie玩一个游戏，有N个石子，Stan先手，两人每次可以从石堆中拿走m个石子，谁拿最后一手，谁赢。其中m的值有范围，每个案例中都设定了m的取值，每次取走石子的个数只能在设定的值中选取，比如一个案例为：21 3 1 3 8，表示石堆中有21个石子，m值可选取的值有3个，分别为1，3和8，也就是每次拿走的石子个数要么是1个，要么是3个，要么就是8个。
解题思路：
动态规划，0-1背包问题，设定dp[i]表示剩下石子个数为 i 时是谁赢，1表示Stan赢，0表示Ollie赢，则状态转移方程的思路就是当 dp[ i - m ] = 0 ...
题目大意：
有n种长宽高为x,y,z的砖头，每种都有无数个。砖头可以用不同方式来盖，砖头a以某种方式可以盖在砖头b上，当且仅当a的底部的长宽都要比b的底部长宽要小。问最高可以建多高？
解题思路：
动态规划中的最长递增（递减）子序列问题，每个砖头可以看成是3个砖头，即A(x,y,z) , B(x,z,y) 和 C(y,z,x)，其中前两个为底，大三个元素为高，然后将所有砖头进行排序，长宽小的排前面，即 (x1 < x2 && y1 < y2 ) || ( x1 < y2 && y1 < x2 ) || ...
题目大意：
给你一个矩阵，当做滑雪场，矩阵的每个单元中的数代表高度，滑雪者只能从高的滑到低的地方，且方向只能是上，下，左和右，问滑雪者最长能滑几个单元？
解题思路：
该题本质上就是求矩阵上的最长严格连续递减（或递增）序列，即序列中的元素不能相等，而且前后之间必须相邻。该题属于动态规划问题，要用到递归。
已找递减序列为例，设dp[i][j]表示第i，j点所构成的序列有多长，求这个值，只需要对其上，下，左和右四个方向进行比较就可以，设board表示题目给的矩阵，dfs( i , j )表示求第i，j个点构成的序列长度，则可以得到
若boar ...
UVA Homer Simpson(10465)
- 博客分类：
- 动态规划
题目大意：
Homer喜欢吃三明治，他吃Krusty三明治需要花m分钟，吃Kwik-e-Mart三明治需要花n分钟，现在给你t分钟，问Homer最多能吃几个三明治，若有剩余时间，则输出剩余时间，输出用空格隔开。
解题思路：
完全背包问题，相当于问t分钟能够由几个m和几个n凑成，之前有硬币凑钱的题目，问的就是使用给定的硬币，有几种方法能够凑到M元，这题类似，只是要算出共需几个m和n才能凑成t分钟，若凑不成，输出剩余时间。只需稍微改一下状态方程：
dp[j] = dp[ j - times[i] ]+ ...
题目大意：
US 的硬币工分为以下五种：penny: 1c, nickel: 5c, dime: 10c, quarter: 25c, half-dollar: 50c，若Mel去商店里买东西，店家找他 N cents，问使用上面5种penny，共有几种找法？即有几种方法能够凑出N cents？
其中0 <= N <= 30000;
解题思路：
完全背包问题，解决方法就是将N从 1 到 30000 中，每个N有几种凑成方法都算一遍。
状态转移方程： dp[j] += dp[ j - coin[i] ]; 即如果j - ...
UVA Coin Change(674)
- 博客分类：
- 动态规划
题目大意：
将一对硬币分成两份，使得两份的总金额差最小。比如有三枚硬币，价值分别为2,3和5，则分成的两堆就是2,3一堆和 5一堆，它们的总金额差为0。
思路：
属于动态规划问题，刚开始看，想到了最大连续子序列和的问题，但又有点不一样。后来发现得用0-1背包来解决。定义一个数组dp[Max]， Max要大一些，表示提供的硬币所能组成的所有和，dp[i]=1表示提供的硬币能够凑成 i ， dp[i]=0表示凑不成 i ， 这样从sum/2往下找，找到最大的，就是这些硬币所能凑成的总和最接近于sum/2的。
代码如下：
#include <ios ...