#
摘要:
#include <iostream>#include <cmath>#include<algorithm>#include<cstring>using namespace std;struct node{ int data;&n...
阅读全文
今天碰到一个最小生成树（数据结构基础算法）
巩固了一下 没有什么大的收获。
不过发现原来在程序后面加个system("pause")也能AC;
代码如下：
#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAX 101
#define INFINITE 1000000000
struct node
{
double a;
double b;
}dot[MAX];
double value[MAX][MAX];
bool visit[MAX];
double dis[MAX];
int n;
double distance(int i,int j)
{
double temp=0;
temp=sqrt((dot[i].a-dot[j].a)*(dot[i].a-dot[j].a)+(dot[i].b-dot[j].b)*(dot[i].b-dot[j].b));
return temp;
}
double prim()
{
double sum=0;
int i,j;
int k;
memset(visit,false,sizeof(visit));
for(i=1;i<=n;i++)
{
dis[i]=value[1][i];
}
visit[1]=true;
int mark;
double test=10000000000;
sum=0;
for(j=1;j<=n-1;j++)
{
test=INFINITE;
for(i=1;i<=n;i++)
{
if(visit[i]==false&&dis[i]<test)
{
test=dis[i];
mark=i;
}
}
sum+=test;visit[mark]=true;
for(i=1;i<=n;i++)
{
if(visit[i]==false&&value[mark][i]<dis[i])
dis[i]=value[mark][i];
}
}
return sum;
}
int main ()
{
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&dot[i].a,&dot[i].b);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
value[i][j]=distance(i,j);
}
}
printf("%.2f\n",prim());
system("pause");
return 0;
}
最近好像跟背包问题有缘啊，已经做了好几道了。不过感觉这个问题确有它值得研究之处，也从中学到不少东西呵＆
这道题目的大意是：有n种材料，每种材料有数量c和长度h还有一个特殊限制（可以看成一个背包的容量）
出题者要你求出用这n种材料可以累加出的最大长度而且其中的每一种材料中的任何一个元素都不能高过这个限制a.想了想，貌似可以用多重背包来形容这个问题，当然我是非专业的，说得不恰当还请大家原谅；
下面的这段代码中有几点值得注意：
首先是这道题中的关键部分和我写的1276题非常相似（参考了网路上大牛的代码 先谢过~)
通过这两个题我发现：这种方法只适用于（这里我们用背包问题的原始定义来形象的说明）物品的重量等于其价值的情况；
非这种情况那就请老老实实按书上的方法做吧（如果说错了 还望您指出，不过我是这样认为的）；
这种方法确实很快，而且比课本上提到的dp方法更牛，一定要掌握呵＆
其次是这道题一定要先排序，再dp;
为什么呢？我想了想 给出下面一个例子：
如果数据是这样的：
2
7 40 3
5 23 1
如果不排序 那么按照那个算法26是不可及的
但是如果排序(按a从小到大）
变成
5 23 1
7 40 3
那么26就可能了
是不是很神奇？但这就是区别 所以本题必须要排序；
我后来又想了想 发现这其实是一个策略的问题，在实际中，我们也当然会把安全的部分放在底层，这总方法感觉上就更稳妥些，而且也带有某种贪心的性质我觉得。
如果哲学的来理解，我引用一句经典的话：九层之台，起于累土，千里之行，始于足下。呵呵，我感觉还挺符合本题的，不知道您觉得呢？
AC CODE:
#include <iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node
{
int h;
int a;
int c;
}a[401];
int cmp(node a,node b)
{
return a.a<b.a;
}
bool dp[40001];
int main ()
{
int n;
int i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].h,&a[i].a,&a[i].c);
}
sort(a+1,a+1+n,cmp);
int max=0;
dp[0]=true;
for(i=1;i<=n;i++)
{
for(k=max;k>=0;k--)
if(dp[k]==true)
{
for(j=1;j<=a[i].c;j++)
{
int temp;
temp=k+j*a[i].h;
if(temp>a[i].a)
break;
dp[temp]=true;
if(temp>max)
max=temp;
}
}
}
printf("%d\n",max);
return 0;
}
摘要: 今天又做了一个背包的题目，有点郁闷~如果单纯只考算法的话应该是很容易的，可是由于数据范围太大，一直都过不了。。。汗~TLE了2个小时，自己尝试了N种剪枝方法但还是过不去。最后无奈只好到网络上搜索了一下，借用了网上大牛代码中的一个剪枝方法，才过掉这道题的。。。刚开始的时候我是这么写的，没有任何剪枝，结果当然是TLE啦：
#include <iostream>#include&...
阅读全文
原题链接：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1546题目的意思很简单，给你一个n进制的数，让你把它转换成m进制，但是有一个限制，如果输出的数字大于7为的话无法在计算器上显示，所以要输出ERROR;
说说做这道题的体会吧，方法很easy,不过感觉代码写的长了点，第一个函数里用了map容器，后来发现其实并没有减少工作量，所以第二的函数里就干脆没使用了 O(∩_∩)O~
所犯的几个错误是 转换成desbase进制是，while循环里应该是num!=0,刚开始的时候写成了num/desbase!=0;呵呵
其次是发现不能在全局状态下往容器里面添加元素。害我总是编译不了，查了半天才知道的。。。
下面是我的代码：
#include <iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
map<char,int>amap;
char temp[100];
int oribase;
int desbase;
int convet(char a[],int oribase)
{
int len=strlen(a);
int i;
int result=0;
for(i=0;i<len;i++)
{
result+=amap[a[len-1-i]]*pow((double)oribase,i);
}
return result;
}
void convet2(int num,int desbase)
{
char test[100];
int i=0;
int testnum;
int len;
while(num!=0)
{
testnum=num%desbase;
num=num/desbase;
if(testnum==15)
test[i]='F';
else if(testnum==14)
test[i]='E';
else if(testnum==13)
test[i]='D';
else if(testnum==12)
test[i]='C';
else if(testnum==11)
test[i]='B';
else if(testnum==10)
test[i]='A';
else if(testnum==9)
test[i]='9';
else if(testnum==8)
test[i]='8';
else if(testnum==7)
test[i]='7';
else if(testnum==6)
test[i]='6';
else if(testnum==5)
test[i]='5';
else if(testnum==4)
test[i]='4';
else if(testnum==3)
test[i]='3';
else if(testnum==2)
test[i]='2';
else if(testnum==1)
test[i]='1';
else if(testnum==0)
test[i]='0';
i++;
}
test[i]='\0';
reverse(test,test+strlen(test));
strcpy(temp,test);
}
int main ()
{
amap['0']=0;amap['1']=1;amap['2']=2;amap['3']=3;
amap['4']=4;amap['5']=5;amap['6']=6;amap['7']=7;
amap['8']=8;amap['9']=9;amap['A']=10;amap['B']=11;
amap['C']=12;amap['D']=13;amap['E']=14;amap['F']=15;
int midresult;
int len;
while(scanf("%s%d%d",temp,&oribase,&desbase)!=EOF)
{
midresult=convet(temp,oribase);
convet2(midresult,desbase);
len=strlen(temp);
if(len>7)
{
printf(" ERROR\n");
}
else
printf("%7s\n",temp);
}
return 0;
}
经典的背包问题.
#include <iostream>
#include <algorithm>
using namespace std;
int w[3500];
int v[3500];
int dp[13000];
int main ()
{
int n,m;
int i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d%d",&w[i],&v[i]);
}
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
for(j=m;j>=w[i];j--)
{
if(dp[j]<dp[j-w[i]]+v[i])
dp[j]=dp[j-w[i]]+v[i];
}
}
printf("%d\n",dp[m]);
return 0;
}
这道题的题意大概是这样的：给出一个字符串，如果将字母表中的26个字母依次映射成数字1-26，这样便形成一个密码，a cipher.学过密码学就知道，这是一个简单的替代密码不过似乎并不是那么好用，虽然加密的确很方便，可是解密就麻烦了，因为存在很多种解密的方法，所以本题就是要你求出一串数字究竟有多少种解密方法。
个人心得：这是我寒假做的最后几道题目的其中一道了，一拿到这道题目我就立刻想到了动态规划，呵呵，看来偶对dp开始有点感觉了；
解本题的关键在于将dp[i]装换成为dp[i-1]和dp[i-2]的关系
首先确定dp[1]和dp[2]的值 前者肯定等于1 而后者可能为2也可能为1 这个应该很容易判断出来
然后在判断i>=3的情况
如果ch[i]为字符‘0’ 那么dp[i]肯定等于dp[i-2].因为一个字符不可能被映射成0，它必须和前一个字符成为一个整体
如果不是字符零，那么看看这个字符与前一个字符是不是能构成一个小于等于26且大于0的数字
并且这个数字的第一位不是0,那么dp[i]=dp[i-1]+dp[i-2];
如果不是让面的两种情况 dp[i]=dp[i-1];
这个题目其实很容易想到，不过刚做的时候没有设出temp变量，只是规定两个数字的范围
'2'>=ch[i-1]>'0'&&ch[i]<='6'这样19就被和谐掉了所以一直调都不对最后才想到的 O(∩_∩)O~
Source Code
Problem: 2033 User: abilitytao
Memory: 272K Time: 16MS
Language: C++ Result: Accepted
#include<iostream>
using namespace std;
long dp[50001];
char ch[50001];
int work(char a[])
{
int temp;
int len;
len=strlen(a);
int i;
dp[0]=1;
temp=(ch[0]-'0')*10+(ch[1]-'0');
if(temp>0&&temp<=26&&ch[1]!='0')
dp[1]=2;
else
dp[1]=1;
for(i=2;i<len;i++)
{
temp=(ch[i-1]-'0')*10+(ch[i]-'0');
if(ch[i]=='0')
dp[i]=dp[i-2];
else if(temp>0&&temp<=26&&ch[i-1]!='0')
dp[i]=dp[i-1]+dp[i-2];
else
dp[i]=dp[i-1];
}
return dp[len-1];
}
int main ()
{
while(cin>>ch)
{
if(ch[0]=='0')
break;
cout<<work(ch)<<endl;
}
return 0;
}
Pku 3620解题报告
一、原题
Description
Farmer John's farm was flooded in the most recent storm, a fact only aggravated by the information that his cows are deathly afraid of water. His insurance agency will only repay him, however, an amount depending on the size of the largest "lake" on his farm.
The farm is represented as a rectangular grid with N (1 ≤ N ≤ 100) rows and M (1 ≤ M ≤ 100) columns. Each cell in the grid is either dry or submerged, and exactly K (1 ≤ K ≤ N × M) of the cells are submerged. As one would expect, a lake has a central cell to which other cells connect by sharing a long edge (not a corner). Any cell that shares a long edge with the central cell or shares a long edge with any connected cell becomes a connected cell and is part of the lake.
Input
* Line 1: Three space-separated integers: N, M, and K
* Lines 2..K+1: Line i+1 describes one submerged location with two space separated integers that are its row and column: R and C
Output
* Line 1: The number of cells that the largest lake contains.
Sample Input
3 4 5
3 2
2 2
3 1
2 3
1 1
Sample Output
4
二．题意阐述
1.其实本题可以转化成如下的纯数学模型。
2.给出n*m大小的矩阵，初始值全为0；
3.在特定的位置将a[i][j]置成1；
4.求取相连的1个数的最大值。
三.算法
此题看似简单，但实际上蕴藏玄机。懂得此法的同学将无疑大大提升自己的能力，再将其拓展，则能够解决一大类问题，此题包含着一个及其重要的数学模型----递归搜索（名字是自己取的，不专业请原谅）。
只要设计一个函数，给一个入口参数(I,j),使得运行该函数后，得到与(I,j)方块相连的方块数。
然后在用循环，将每一个方块都找一遍，求出最大值即可。
那个函数，这是本题的精髓，用递归的方法，可以让其自动朝着四周的方向搜索满足条件的方块，直到求出与某一格相连的小方块数目的总数。
其实，我一直想把上回的超级玛丽做出来，这个题给了我基本的搜索本领。我想，只要我继续研究下去就一定能解决超级玛丽的问题了 o(∩_∩)o…
四、解题过程
本来想用循环的方法来做的，可是发现用循环貌似无法结束查找。于是我请教了陈泽怡学长，他提示我用递归的方法来解此题，这才使我恍然大悟。用递归可以不断地调用函数体本身，直到结束查找！~
五.程序代码
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int a[101][101]={0};
int num;
void search(int i,int j)
{
if(a[i][j]==1)
{
a[i][j]=-1;
num++;
search(i,j+1);
search(i+1,j);
search(i,j-1);
search(i-1,j);
}
}//定义递归搜索函数，入口参数为所要调查的小方块位置
int main()
{
int n,m,k,i,j,x,y,max=0;
cin>>n>>m>>k;
for(i=1;i<=k;i++)
{
cin>>x>>y;
a[x][y]=1;//把要调查的位置置为1；
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
num=0;
search(i,j);
if(num>=max)
max=num;
}//用循环的方法将整个矩阵都查找一遍，并求出与某小方块相连方块数的最大值；
cout<<max<<endl;//输出该最大值；
return 0;
}
六．小结
这道题的代码看上去很短，但是确非常非常的重要，当然 ，这并不代表我完全掌握了这类方法，如果说不是深度或者广度优先怎么办，如何用队列？这是接下来我需要面对和解决的问题…另外，我写报告的水平有待提高，如果不是知道我的意图，会有人看得懂这份报告么？ACM讲究的是团队作战，即使我很优秀 ，也不过是个独断独行的人，这是不能成功的，要想取得成绩，先得学会与同学交流。
呵呵 这是我的第一篇结题报告 值得纪念啊 当然还要特别感谢贾琼学姐哦 O(∩_∩)O~
摘要:
//Copyright by abilitytao//All right not reserved!! #include <process.h>#include <iostream.h>#include <conio.h>#include&nbs...
阅读全文