ITeye博客

Sword and Flame

SwordAndFlame · 共 9 篇文章

树型DP 父子兄弟结构 poj 2342 Anniversary party

#include <iostream> #include <cstdio> #include <cstring> struct Tree{ int father; int child; int brother; int NOT; int s; int Max(){ return s > NOT ? s : NOT; } void Init(){ father=child=brother=NOT=0; } }tree[60001]; void dfs(int v) { int child; child=tree[v].child; while(child){ dfs(child); tree[…

2011-09-08 11:36 · 动态规划 · 评论(0)

完全背包 poj 2063 Investment

#include <iostream> #include <cstdio> #include <cstring> using namespace std; int c[20]; int I[20]; int dp[50050]; int main() { int rest,capital,t,year,bnum; scanf("%d",&t); while(t--) { rest=0; capital=0; year=0; bnum=0; scanf("%d%d",&capital,&year); scanf("%d",&bnum); for(int i=0;i<bnum;i++) { sc…

2011-09-06 09:06 · 动态规划 · 评论(0)

快速幂取模

lld exp_mod(lld a,lld b,lld c) { lld ans=1; lld temp=a%c; if(b==0) return 1; while(b) { if(b&1) ans=ans*temp%c; temp=temp*temp%c; b>>=1; } return ans; }

2011-08-21 22:48 · 数学之美 · 评论(0)

数位dp_HDOJ_3555_bomb

Bomb Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 876 Accepted Submission(s): 319 Problem Description The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the tim…

2011-08-19 22:05 · 动态规划 · 评论(0)

位运算

统计1的个数 int count(int x) { int res=0; while(x){ res++; x&=x-1; } return res; }

2011-08-15 10:40 · 位运算 · 评论(0)

旋转卡壳

http://www.cppblog.com/staryjy/archive/2010/09/25/101412.html

2011-08-15 09:05 · 计算几何 · 评论(0)

DP基础之LCS

#include <iostream> #include <string> using namespace std; int dp[1050][1050]; int main() { string a,b; while(cin>>a>>b) { memset(dp,0,sizeof(dp)); for(int i=1;i<=a.size();i++) { for(int j=1;j<=b.size();j++) { if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1; else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); }…

2011-08-14 21:53 · 动态规划 · 评论(0)

编辑距离

编辑距离; 来自wiki的编辑距离介绍 编辑距离 ,又称 Levenshtein距离 ,是指两个 字串 之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个 字符 ,删除一个字符。 例如将kitten一字转成sitting: sitten (k→s) sittin (e→i) sitting (→g) 俄罗斯 科学家 Vladimir Levenshtein 在 1965年 提出这个概念。 编辑距离的经典动态规划算法: 初始化: 字符串 Levenshtein距离(字符 str1[1..lenStr1], 字符 str2[1..lenStr2]…

2011-08-05 18:20 · 动态规划 · 评论(0)

我的进度

代码能力:50+; 动态规划: 数位dp:HDOJ 3555 bomb 简单数位dp: http://acm.hdu.edu.cn/showproblem.php?pid=3555 dp中的双向问题:2 编辑距离:1; LIS类问题;2; POJ 1887 Testing the CATCHER http://poj.org/problem?id=1887 POJ 2533 Longest Ordered Subsequence http://poj.org/problem?id=2533 LCS问题:1; poj-1159-Palindrome http://poj.org/problem…

2011-08-01 21:16 · 高手之路 · 评论(0)