文章列表
这道题目的思路和poj1753的思路一样。
有所不同的是这道题目中还需要输出搜索的路径，于是在unit中加了一个pre变量以记录搜索的路径，最后通过递归调用print_detail从前往后输出宽搜的结果。
Problem: 2965 User: godfrey90
Memory: 1992K Time: 1000MS
Language: G++ Result: Accepted
Source Code
#include<cstdio>
struct unit {
int x;
int rounds;
int i;
int pre;
};
...
1.声明定义与内存分配
1.1一个由c/C++编译的程序占用的内存分为以下几个部分
(1)栈区（stack）—由编译器自动分配释放，存放函数的参数值，局部变量的值等。
(2)堆区（heap）—一般由程序员分配释放，若程序员不释放，程序结束 ...
#include <iostream>
using namespace std;
struct S
{
int a;
char b;
int c;
char d;
char e;
int f;
double g;
int h;
};
int main()
{
S s;
s.a = 10;
s.b = 'b';
s.c = 30;
s.d = 'd';
s.e = 'e';
s.f = 60;
s.g = 70.0;
s.h = 80;
cout<<sizeof(s)<&l ...
引入
首先来说说“状态压缩动态规划”这个名称，顾名思义，状态压缩动态规划这个算法包括两个特点，第一是“状态压缩”，第二是“动态规划”。
状态压缩：
从状态压缩的特点来看，这个算法适用的题目符合以下的条件：
1.解法需要保存一定的状态数据（表示一种状态的一个数据值），每个状态数据通常情况下是可以通过2进制来表示的。这就要求状态数据的每个单元只有两种状态，比如说棋盘上的格子，放棋子或者不放，或者是硬币的正反两面。这样用0或者1来表示状态数据的每个单元，而整个状态数据就是一个一串0和1组成的二进制数。
2.解法需要将状态数据实现为一个基本数据类型，比如int，long等等，即所谓的状态压缩。状态压 ...
又是一道状态压缩动态规划的题目，于之前一道有异曲同工之妙，成功AC。
1.算法
(1)首先这道题目和之前的那道炮兵阵地类似，可以以行作为划分进行动态规划，后一行根据前一行的状态来确定。
(2)动态规划最重要的是找状态转移方程。就这道题来说，一共是n行，m列。我们可以这样考虑：我们一行一行的放1*2的牌，在第i行放完以后，必须保证该行所有的格子被填满了。这时记录下第i行向第i+1行凸出的地方。即如果有向第i+1行的凸出，就记录为1，否则记录0，这样就用一个m位的2进制数记录了第i行放完后的状态。比如说00110100就说明第2，4，5的位置向下凸出了。然后开始处理第i+1行，可以根据第i行记录的状 ...
AC这道牛B的题目，开心。虽然WA了4次，RE了2次。
1.算法
经典的状态压缩动态规划题。让我慢慢道来：
(1)首先，看到这个题目想到的是暴力搜索，无所谓深搜还是宽搜，都需要对所有的情况进行穷举，10*100的格子，这样穷举的话 ...
1. 按状态类型分
写在前面：
从状态类型分，并不表示一题只从属于一类。其实一类只是一种状态的表示方法。可以好几种方法组合成一个状态，来解决问题。
1.1. 编号（长度）动态规划
共性总结
本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。
一般来说，有两种编号的状态：
状态(i)表示前i个元素决策组成的一个状态。
状态(i)表示用到了第i个元素，和其他在1到i-1间的元素，决策组成有的一个状态。
题库
a) 最长不下降子序列
以一元组(i)作为状态，表示第i个作为序列的最后一个点的时候的最长序列。于是很容易想到O(n2)得算法。但本题可合理组 ...
在ACM题库中，不管是文件输出（输入）还是标准输出（输入），都有着一定的格式，下面我就以杭电1089——1096为例子，简单的介绍一下。
第一种：A+B for Input-Output Practice (I)
【输入】有多组输入数据，但没有具体的告诉你有多 ...
1.算法
核心是宽度优先搜索和位处理。要找出最快的步数，用宽搜。
(1)宽度优先搜索数据结构：
队列的单元unit包含x（用int的末16位记录16个位置的信息），rounds（记录第几轮达到当前的状态），i（记录该状态是通过翻动哪个棋子得来的，以避免返回先前的状态）。queue是一个队列，记录所有状态；p，q分别是队列的头尾指针。used记录已经存在的状态。
(2)宽度优先搜索算法处理：
a.首先是读入数据。
b.进行宽度搜索，直到找到结果，或者队列中没有元素（此时为impossible）。
c.flip函数是从a状态通过翻动第i个棋子到达b状态。
d.在得到一个新状态的时候要检验之前时候存在 ...
1.算法
无，简单计算
2.实现
(1)注意c++库和c库的巧妙运用，本题要求一次读入一行。故用getline()比scanf()更好用，所以选择c++输入库<iostream>。getline()用法getline(cin,str);
(2)c++中string是一个类，长度为str.length()，需要引入的头文件是<string>
c中是char[] 表示string，长度用strlen(str),需要引入的头文件是<cstring>
3.代码
#include<iostream>
#include<string>
us ...
1.算法
很简单，就是读取3个数a，d，n，从a，a+d,a+2d等等中找素数，直到找到第n个
2.实现
运用判断素数的方法
3.代码
#include<cstdio>
#include<cmath>
bool is_prime(int num);
int main()
{
int a,d,n;
scanf("%d%d%d",&a,&d,&n);
while(!((a==0)&&(d==0)&&(n==0)))
{
int count=n;
int result = a;
...
1.算法
本题是给出一个树的先序和中序，输出它的后序。可以通过递归实现。
举例说明
先序：DBACEGF 中序：ABCDEFG
（1）把整个7个字符作为一段，根据先序找出第一个根D，根据中序可以得出，D左边为ABC，右边为EFG。
（2）对D两边递归进行（1）操作。
（3）递归的终止条件是这一段中只有一个字符（即为叶结点）
根据以上可以步骤可以生成一棵树，然后递归输出后序。
ps：
后来发现可以不用生成树的结构，直接递归完成，即在生成树的递归函数中进行后序输出。
2.实现
（1）对于没有给定行的输入可以用 while(cin>>str1>>str2)进行判断，对于如何用s ...
1.算法
题目比较简单，就是简单的高精度加法，一位一位的，加，进位，即可。
2.实现
result数组用来放结果，input用来放输入，没此将输入加到结果上。注意，最后去掉前面所有的0
3.代码
#include<cstdio>
#include<cstring>
int main()
{
int result[10000]={0};
int length=0;
char input[100];
scanf("%s",input);
while(!((strlen(input)==1)&&(input[0]=='0')) ...
C语言中常用预定义的数据类型:
类型： char short int long float double (long double)
大小（字节数）：
gcc3.2.2： 1 2 4 4 4 8 12
Visual C++:1 2 4 4 4 8 8
ARM ...
1.算法
原打算用筛法进行打出素数表，但是这样会超时，于是选取直接判断素数的方法。（在范围比较大的时候，可能用不到那么多的素数，打素数表反而更费时间，直接判断素数的方法看似比较慢，但是省略了前面很大一段打素数表的时间）。接着便是简单的遍历，因为不会出现wrong的情况，故很快找到结果。
2.实现
(1)之前想用c++文件输入输出的时候，发现要加上using namespace std,因为C＋＋标准程序库中的所有标识符都被定义于一个名为std的namespace中。具体参见http://www.kuqin.com/language/20080107/3532.html
3.代码
#includ ...