思路见前一文，上一种做法中，内存差一点就超了，改进了一下，因为求LCS时，只用到了表的两行，所以可以进行空间压缩
//196K
797MS
#include <stdio.h>
#include <string.h>
#define M 5002
short int c[2][M];
char s1[M],s2[M];
int Max (int a,int b)
{
return a
> b ? a : b;
}
int DP (int n)
{
int
i,j,k;
for (i = 0;
i <= n; i ++)
c[0][i] = 0;
k = 1;
for (i ...
阅读全文
题意：有一长为L的message 和W个word in the dictionary 。要求去除message中的某些字符使其由the
word of the dictionary 组成 （当然，要求是去掉最少的）
原文地址：http://blog.csdn.net/lyy289065406/article/details/6648121
思路：
dp[i]表示从message中第i个字符开始，到第L个字符（结尾处）这段区间所删除的字符数，初始化为dp[L]=0
由于我的程序是从message尾部向头部检索匹配，所以是下面的状态方程：
从程...
阅读全文
题意：有n(1~10)种不同颜色的衣服总共m
(1~100)件，Dearboy和她的girlfriend两个人要一起洗完全部衣服，
两个人洗衣速度相同，并且已知每件衣服需要的时间<1000)。
两个人可以同时洗衣。为了预防色彩混合，必须一种颜色的衣服洗完之后，两个人才能开工洗下一种颜色的衣服，问两个人洗完所有的衣服需要的最短时间。
思路：每种颜色的衣服可以分开来考虑，算出每种颜色的衣服所需要的最短时间，最后加起来即可。
然后再来...
阅读全文
题目大意：
有一个天平，天平左右两边各有若干个钩子，总共有C个钩子，有G个钩码，求将钩码全部挂到钩子上使天平平衡的方法的总数。
其中可以把天枰看做一个以x轴0点作为平衡点的横轴
输入：
2 4 //C 钩子数 与 G钩码数
-2 3 //负数：左边的钩子距离天平中央的距离；正数：右边的钩子距离天平中央的距离c[k]
3 4 5 8 //G个重物的质量w[i]
dp思路：
每向天平中方一个重物，天平的状态就会改变，而这个状态可以由若干前一状...
阅读全文
题意：有一个Cash
Machine，里面装有n种面值为n[i]的货币，每种有v[i]张。问在所换金额不超过cash元钱的情况下，所能换取的最大金额。
思路：原版多重背包模版，直接用就行，不理解的看一多重背包的讲解（很详细）
//556K
47MS
#include <stdio.h>
#include <string.h>
#define M 100010
#define N 15
int dp[M],count[N],val[N];
int money;
int max (int a,int b)
{
return a
> b ? a : b;
}
void...
阅读全文
题意：cow 想要在太空搭电梯，每一种block有它的高度hi和最高不能超过多高ai 每种block有一定的数量ci
求能搭建的高大高度
思路：多重背包。 只是有一点小变形 把block按它的的ai从小到大排序，从小的开始搭建 因为如果从大的开始，就有可能把小的给忽略掉
用dp[] 记录状态 能否达到这个高度 然后在每次比较时 选出当前能达到的最大高度
//332K
172MS
#include <stdio.h>
#include <string.h>
#include <...
阅读全文
POJ == 北京大学ACM在线评测系统 http://acm.pku.edu.cn/JudgeOnline
1. 标记 难 和 稍难的题目大家可以看看，思考一下，不做要求，当然有能力的同学可以直接切掉。
2. 标记为 A and B 的题目是比较相似的题目，建议大家两个一起做，可以对比总结，且二者算作一个题目。
3. 列表中大约有70个题目。大家选做其中的50道，且每类题目有最低数量限制。
4. 这里不少题目在 BUPT ACM FTP 上面都有代码，请大家合理利用资源。
5. 50...
阅读全文
首先赞一下题目， 好题
题意：
Marjar University has decided to upgrade the infrastructure of school intranet by using fiber-optic technology. There are N buildings in the school. Each building will be installed
with one router. These routers are connected by optical cables in such a way that there is exactly one path between any two routers.
Each router should be initialized with an operatin...
阅读全文
![[poj 3853]Loops[概率DP入门题]](https://admin.xuebuyuan.com/wp-content/themes/HotNewspro/images/random/5.jpg)
这种题主要就是推状态转移方程..推公式
解析：
设dp[i][j]表示(i,j)到(R,C)需要消耗的能量[这个定义很重要!]
则：
dp[i][j]=p1[i][j]*dp[i][j]+p2[i][j]*dp[i][j+1]+p3[i][j]*dp[i+1][j]+2;(走一步,额外消耗能量2)
化简得到：
dp[i][j]=p2[i][j]*dp[i][j+1]/(1-p1[i][j])+p3[i][j]*dp[i+1][j]/(1-p1[i][j])+2/(1-p1[i][j]);
注意一种情况就是p1[i][j]==1的情况。(除0错误)
题目只是保证答案小于1000000.但是有的点可能永远都不...
阅读全文
//反过来找比较简单
#include <cstdio>
#include <iostream>
#include <string.h>
using namespace std;
double map[110][110];
double weight[110];
double dist[110];
void dijkstar(int sta,int n)
{int i,j,mark;double maxi;bool flag[100];memset(flag,0,sizeof(flag));memset(dist,0,sizeof(dist));flag[sta]=1;dist[sta]=1;for(i=1;i<=n;i++){maxi=-1;for(j=1;j<=n;j++){if(!flag[j]){if(map...
阅读全文