博文
PKU 1050 动态规划-解决最大子矩阵问题【转】(2009-09-17 14:47:00)
摘要：
最大子矩阵问题：
问题描述：(具体见http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1050)
给定一个n*n(0<n<=100)的矩阵，请找到此矩阵的一个子矩阵，并且此子矩阵的各个元素的和最大，输出这个最大的值。
Example：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
其中左上角的子矩阵：
9 2
-4 1
-1 8
此子矩阵的值为9+2+(-4)+1+(-1)+8=15。
我们首先想到的方法就是穷举一个矩阵的所有子矩阵，然而一个n*n的矩阵的子矩阵的个数当n比较大时时一个很大的数字 O(n^2*n^2)，显然此方法不可行。
怎么使得问题的复杂度降低呢？对了，相信大家应该知道了，用动态规划。对于此题，怎么使用动态规划呢？
让我们先来看另外的一个问题(最大子段和问题)：
给定一个长度为n的一维数组a，请找出此数组的一个子数组,使得此子数组的和sum＝a[i]+a[i+1]+……+a[j]最大，其中i>=0,i<n,j>=i,j<n，例如
31 -41 59 26 -53 58 97 -93 -23 84
子矩阵59+26-53+58+97=187为所求的最大子数组。
第一种方法－直接穷举法:
maxsofar=0;
for i = 0 to n
{
for j = i to n
{
sum=0;
&......
PKU 1018 看不明白题目耶······(2009-09-17 13:50:00)
摘要：
郁闷。连题目都看不明白···········
哪位朋友可以给我讲讲题目意思吗？
谢啦！......
PKU ACM 1319--Pipe Fitters(2009-09-16 23:50:00)
摘要：
#include<iostream>
#include<cmath>
using namespace std;
int grid(float width,float height)// use string ???
{
int h=(int)height;
int w=(int)width;
return h*w;
}
int skew1(float width,float height)
{
int m1=(int)(width-0.5),n1=(int)((2*(height-1)/sqrt(3.0))+1);
int m2=(int)(height-0.5),n2=(int)((2*(width-1)/sqrt(3.0))+1);
return m1*n1>m2*n2? m1*n1:m2*n2;
}
int skew2(float width,float height)
{
int m1=(int)width,n1=(int)((2*(height-1)/sqrt(3.0))+1);
int m2=(int)height,n2=(int)((2*(width-1)/sqrt(3.0))+1);
int N1,N2;
if(n1%2==0)
N1=int(m1*n1-n1/2);
else
N1=int(m1*n1+n1/2-0.5);
if(n2%2==0)
N2=int(m2*n2-n2/2);
else
N2=int(m2*n2+n2/2-0.5);
return N1>N2? N1:N2;
}
int main()
{
float w,h;
int max=0;
while(cin>>w>......
PKU 北大ACM详解 转自百度百科(2009-09-16 21:57:00)
摘要：PKU 北大ACM详解 转自百度百科
2009-04-09 04:27 P.M.
北大ACM题分类
主流算法：
1.搜索 //回溯
2.DP（动态规划）
3.贪心
4.图论 //Dijkstra、最小生成树、网络流
5.数论 //解模线性方程
6.计算几何 //凸壳、同等安置矩形的并的面积与周长
7.组合数学 //Polya定理
8.模拟
9.数据结构 //并查集、堆
10.博弈论
1、 排序
1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379,
1002（需要字符处理，排序用快排即可） 1007（稳定的排序） 2159（题意较难懂） 2231 2371（简单排序） 2388（顺序统计算法） 2418（二叉排序树）
2、 搜索、回溯、遍历
1022 1111d 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 2386 1010,1011,1018,1020,1054,1062,1256,1321,1363,1501，1650,1659,1664,1753,2078
,2083,2303,2310,2329
简单：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426,
不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 2349,
推荐：1011, 1......
PKU ACM 1013 Counterfeit Dollar(2009-09-16 21:41:00)
摘要：#include <iostream>
#include <string>
using namespace std;
struct input{
string left;
string right;
string state;
}in[3];
bool Light(char &ch)
{
for(int i=0;i<3;i++)
{
switch(in[i].state[0])
{
case 'u':
if(in[i].right.find(ch)==string::npos)
return true;
break;
case 'd':
if(in[i].left.find(ch)==string::npos)
return true;
break;
case 'e':
if(in[i].left.find(ch)!=string::npos||in[i].right.find(ch)!=string::npos)
return true;
break;
default:
return false;
}
}
return false;
}
bool Heavy(char &ch)
{
for(int i=0;i<3;i++)
{
&......
PKU 1061 (扩展欧几里德)(2009-09-13 00:41:00)
摘要：
所谓扩展欧几里德,就是在欧几里德算法的基础上加入变量X,Y,使得aX-bY=GCD(a,b)。
此时X，Y是该不定方程式的一组解。
求a * x + b * y = n的整数解的过程:
1、先计算Gcd(a,b)，若c不能被Gcd(a,b)整除，则方程无整数；否则，在方程两边同时除以Gcd(a,b)，得到新的不定方程a' * x + b' * y = n'，此时Gcd(a',b')=1;
2、利用上面所说的欧几里德算法求出方程a' * x + b' * y = 1的一组整数解x0,y0，则n' * x0,n' * y0是方程a' * x + b' * y = n'的一组整数解；
3、根据数论中的相关定理，可得方程a' * x + b' * y = n'的所有整数解为：
x = n' * x0 + b' * t
y = n' * y0 - a' * t
(t为整数)
上面的解也就是a * x + b * y = n 的全部整数解。
关于1061的解法
由题意:
(x+mt)-(y+nt)=pL
=>(m-n)t-(y-x)=pL
=>(m-n)t-pL=(y-x) 即 (m-n)t≡(y-x)MOD(L)
令a=m-n,b=L,c=y-x,X=t,Y=p
则原等式转换为 aX-bY=c
使用扩展欧几里德 求出一组解X0,Y0=>aX0-bY0=GCD(a,b)
令d=GCD(a,b) 若c%d!=0 则无解
......
PKU ACM各题算法分类(2009-09-11 09:31:00)
摘要：
POJ各题算法分类
动态规划：
1037 A decorative fence、1050 To the Max、1088 滑雪、1125 Stockbroker Grapevine、1141 Brackets Sequence、1159 Palindrome、1160 Post Office、1163 The Triangle、1458 Common Subsequence、1579 Function Run Fun、1887 Testing the CATCHER、1953 World Cup Noise、2386 Lake Counting
简单、模拟题：
1001 Exponentiation 、1002 487-3279、1003 Hangover 、1701 Dissatisfying Lift、2301 Beat the Spread!、2304 Combination Lock、2328 Guessing Game、2403 Hay Points 、2406 Power Strings、2339 Rock, Scissors, Paper、2350 Above Average、2218 Does This Make Me Look Fat?、2260 Error Correction、2262 Goldbach\'s Conjecture、2272 Bullseye、2136 Vertical Histogram、2174 Decoding Task......
CScrollView的使用(2009-09-09 21:33:00)
摘要：
下面贴两段CScrollView的使用！希望有帮助。后面的方法我会陆续试用的。
CScrollView这个类用于需要滚动条的场合。我们可以直接用向导生成，在选择视图类的基类时选择CScrollView即可。
如果我们的程序原来用的是CView类，此时想改成CScrollView类，需要稍微做一下修改。
CView-->CScrollView
利用ClassWizard，在CxxView類別中，建立OnInitialUpdate( ) member function
void CxxView::OnInitialUpdate()
{
CScrollView::OnInitialUpdate();
SetScrollSizes(MM_TEXT, CSize( 800, 600 ) );
}
cpp中:
IMPLEMENT_DYNCREATE(CxxView, CScrollView)
BEGIN_MESSAGE_MAP(CxxView, CScrollView)
如何在对话框中使用CScrollview类( 转 )
CRect rectWindow;
GetWindowRect(rectWindow);
CRuntimeClass *pViewClass = RUNTIME_CLASS(CMyScrollView);
CCreateContext * pContext;
pContext = new CCreateContext;
pContext->m_pCurrentDoc = NULL;
pContext->m_pCurrentFrame = NULL;
pContext->m_pLastView = NULL;
pContext->m_pNewDocTemplate =NULL;
pContext->m_pNewViewClass = pViewClass;
CWnd * pWnd = NULL;
pWnd = DYNAMIC_DOWNCAST(CWnd,pViewClass->CreateObject());
pWnd -&g......
ACM基本算法分类、推荐学习资料和配套pku习题(2009-09-08 00:13:00)
摘要：
一.动态规划
参考资料：
刘汝佳《算法艺术与信息学竞赛》《算法导论》
推荐题目：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1141
简单
http://acm.pku.edu.cn/JudgeOnline/problem?id=2288
中等，经典TSP问题
http://acm.pku.edu.cn/JudgeOnline/problem?id=2411
中等，状态压缩DP
http://acm.pku.edu.cn/JudgeOnline/problem?id=1112
中等
http://acm.pku.edu.cn/JudgeOnline/problem?id=1848
中等，树形DP。可参考《算法艺术与信息学竞赛》动态规划一节的树状模型
http://acm.zju.edu.cn/show_problem.php?pid=1234
中等，《算法艺术与信息学竞赛》中的习题
http://acm.pku.edu.cn/JudgeOnline/problem?id=1947
中等，《算法艺术与信息学竞赛》中的习题
http://acm.pku.edu.cn/JudgeOnline/problem?id=1946
中等，《算法艺术与信息学竞赛》中的习题
http://acm.pku.edu.cn/JudgeOnline/problem?id=1737
中等，递推
http://acm.pku.edu.cn/JudgeOnline/problem?id=1821
中等，需要减少冗余计算
http://acm.zju.edu.cn/show_problem.php?pid=2561
中等，四边形不等式的简单应用
http://acm.pku.edu.cn/JudgeOnline/problem?id=1038
较难，状态压缩DP，《......
Eclipse入门: Eclipse的使用简介及插件开发(2009-09-06 23:08:00)
摘要：http://www.ibm.com/developerworks/cn/java/l-eclipse/index.html
Eclipse 是替代IBM Visual Age for Java（以下简称IVJ）的下一代IDE开发环境，但它未来的目标不仅仅是成为专门开发Java程序的IDE环境，根据Eclipse的体系结构，通过开发插件，它能扩展到任何语言的开发，甚至能成为图片绘制的工具。目前，Eclipse已经开始提供C语言开发的功能插件。更难能可贵的是，Eclipse是一个开放源代码的项目，任何人都可以下载Eclipse的源代码，并且在此基础上开发自己的功能插件。也就是说未来只要有人需要，就会有建立在Eclipse之上的COBOL，Perl，Python等语言的开发插件出现。同时可以通过开发新的插件扩展现有插件的功能，比如在现有的Java开发环境中加入Tomcat服务器插件。可以无限扩展，而且有着统一的外观，操作和系统资源管理，这也正是Eclipse的潜力所在。
虽然目前Eclipse项目还没有最后完成，但从已有的版本中已经能领略到Eclipse设计主导思想和主要功能特点。现在就了解Eclipse不但能使广大程序员对这款业界期望很高的IDE能一睹为快，更为重要的是如果能参加到Eclipse项目的开发中或是阅读它的开放源代码，这对广大程序员来说无疑是一个千载难逢的提高编程水平的好机会。Eclipse计划提供多个平台的版本，象Windows，Linux，Solaris，HP-UX和AIX，以下只介绍Windows版本。本文第一部分先介绍Eclipse的基本使用方法。第二部分介绍如何进行Eclipse的插件开发。
一．Eclipse简介
Eclipse是开放源代码的项目，你可以到 www.eclipse.org去免费下载Eclipse的最新版本，一般Eclipse提供几个下载版本：Release，Stable Build，Integration Build和Nightly Build，建议下载Release或Stable版本，笔者用的是Build20020125（Stable版本）。Eclipse本身是用Java语言编写，但下载的压缩包中并不包含Java运行环境，需要用户自己另行安装JRE，并且要在操作系统的环境变量中指明JRE中bin的路......