D10

=-=今天被dev-c++坑到死..简直
晚上准备怒装liunx..

T1:数论

一开始碰到的是T1的运算符优先问题吧..maybe..但是我加上括号了还是WA啊..后面把式子拆开写才A了..次奥
附上代码以此为戒:
错误代码
m=(e-s)/t+1;
ans=((2+(m-1)*d)*m)/2;
tot+=ans;
 正确的代码!
m=(e-s)/t+1;
ans=2+(m-1)*d;
ans*=m;
ans/=2;
tot+=ans;
呵呵我一脸啊..简直
真是不懂怎么了...

T2:正解 DP

骗分:DFS+剪枝

表示还是很感谢这一题..让我学会了用DFS打暴力,算是有所领会了吧

但是dev-c++和PSACAL在写DFS上有些差异,就是在于
int search(int x,int y,int t){
if(t==n+1){
tot=x*x*x*x+y;
if(tot<minx) minx=tot;
return minx;
}else{
search(x+a[t],y,t+1);
search(x,y+b[t],t+1);
}
return minx;
}
 p不需要最后的return minx;

QAQ可是c++要是没有写这一行,就会没有返回值

以及最后调用 search(0,0,0)

坑爹的是dev-c++不会显示这样的错误,于是就出现了手动输入数据可以得出正确答案,但是用cena就是过不去的情况...
悲愤啊...
MARK:
如果自己用linux不习惯,还是得用dev-c++的话,
记得要开-wall
具体位置在tool-compiler options-settings-warnings-YES

对于正解:DP

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=2147483247;
long long n,m,t,a[100],b[100],f[100][151],minx,ans = INF,tot;
//f[i][j]表示前i个路段,使用j个红苹果的时候,使用青苹果最少的个数
int main(){
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
memset(f,63,sizeof(f));
scanf("%d%d",&t,&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
}
f[0][0]=0;//初始化
f[1][a[1]]=0;//
f[1][0]=b[1];//
for(int i=2;i<=n;i++)
for(int j=0;j<=150;j++){
if(j-a[i]>=0) f[i][j]=min(f[i-1][j]+b[i],f[i-1][j-a[i]]);
else f[i][j]=f[i-1][j]+b[i];
}
for(int i=0;i<=150;i++){
if(ans>f[n][i] + i*i*i*i) ans=f[n][i]+i*i*i*i;
}
printf("%lld",ans);
}

 mark几个地方:
1.这个的主要思想是01背包,不过要注意这里有后效性,不能直接套用;
2.故这里要注意一下初始化
3.j-a[i]的情况要讨论..注意
4.最后记得for一遍过去,得出答案
5.当然最重要的,还是要会写状态转移方程..以及..DP就是这么回事..要有自信嗯! T3:BFS
其实仔细分析会发现这是一题很简单的广搜啊...
只不过是个三维坐标而已...
和二维的一样打就可以了...
不过我的程序不懂为什么会WA..
这里附上错误的代码,希望自己有一天可以发现错误啊><
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int dx[6]={-1,0,0,0,0,1},dy[6]={0,1,0,0,-1,0},dz[6]={0,0,1,-1,0,0};
int d1[1000001],d2[1000001],d3[1000001];
long long n,m,l,w,h,tot=0;
long long f[51][51][51];
bool vis[51][51][51];
int abs(int x){
return x<0?-x:x;
}
void search(int i,int j,int k){
int h=1,w=1;
int x,y,z,xx,yy,zz;
vis[i][j][k]=0;
d1[h]=i;d2[h]=j;d3[h]=k;
while(h<=w){
x=d1[h];y=d2[h];z=d3[h];
for(int i=0;i<=5;i++){
xx=x+dx[i];
yy=y+dy[i];
zz=z+dz[i];
if(abs(f[xx][yy][zz]-f[x][y][z])<=n && vis[xx][yy][zz] && xx<=l && yy<=w && zz<=h && xx>=0 && yy>=0 && zz>=0){
vis[xx][yy][zz]=0;
w++;
d1[w]=xx;
d2[w]=yy;
d3[w]=zz;
} }
h++;
}
}
int main(){
//freopen("engineer.in","r",stdin);freopen("engineer.out","w",stdout);
scanf("%d%d%d",&l,&w,&h);
scanf("%d",&n);
memset(vis,true,sizeof(vis));
for(int i=1;i<=l;i++)
for(int j=1;j<=w;j++)
for(int k=1;k<=h;k++) scanf("%d",&f[i][j][k]);
for(int i=1;i<=l;i++)
for(int j=1;j<=w;j++)
for(int k=1;k<=h;k++){
if(vis[i][j][k]){
tot++;
search(i,j,k);
}
}
printf("%d",tot);
return 0;
}
T4:spfa
先对feli作BFS,找出feli到每个地方的最短距离,然后模拟japan行动判断什么时候两人相遇。相遇的时间,就是花去的最短时间。 注意内存限制..只有1M
今天本来想改完的...可惜时间又浪费了 哼!连hpy都改完了..我也应该要改完!
一定要在xc回来之后,让他刮目相看啊.....
上一篇:Word 中实现公式居中编号右对齐 -- 含视频教程(9)


下一篇:vi编辑器的基本使用