16/7/2012 ICPC培训 第一天
这是我首次参加此类培训。心里还是有点小激动的。
据说明天下午培训内部会有一场小比赛，希望自己给力呀。
汇报下今天吧：
1、看了4道题，刷了3道题。
其中，前2道是上午做出来的。
第一道是水题（HDU1201），讲究的是对一些基本知识的把握，没有啥太难的算法。
第二题是01背包（HDU1203），和往常不一样的是这里算的是概率，还要反着想。你要算至少拿到
一个学校的offer最大概率，可以1 - 一个学校的offer也拿不到的最小概率。
第三题（HDU1203）的直接没思路不了，真的一点也没有，然后就睡觉了。没想到一睡一下午呀
！
然后晚上又刷了一道（HDU1208），本以为用的是搜索，但超时了。想不到好办法，找度娘了。
两种解决办法：DP或者记忆化搜索。神马呀......
（推荐大家看看，有关DP和记忆化搜索的比较：点击打开链接）
2、1201和1203完全独立完成，有点小成就感。1208似懂非懂的。可恶的DP。
3、上代码：
1201：点击打开链接
1203：
#include<iostream>#include<iomanip>using namespace std;const int MAX=10000;struct school{ int money; double ratio;}node[MAX];void input(int c){ for(int i=0;i<c;i++) { scanf("%d%lf",&node[i].money,&node[i].ratio); node[i].ratio=1-node[i].ratio; }}double zeroOnePack(int s,int c) { double temp[MAX+10]; //memset(temp,1,sizeof(temp)); for(int k=0;k<=s;k++) { temp[k]=1; } //01背包的核心部分 for(int i=0;i<c;i++) { for(int j=s;j>=node[i].money;j--) { temp[j]=(temp[j]>temp[j-node[i].money]*node[i].ratio)?temp[j-node[i].money]*node[i].ratio:temp[j]; } } return 1-temp[s];}int main(){ int sumMoney,chances; while(cin>>sumMoney>>chances,sumMoney||chances) { input(chances); cout<<setiosflags(ios::fixed)<<setprecision(1)<<zeroOnePack(sumMoney,chances)*100; printf("%%\n"); } return 0;}
1208：
1、DP
#include<iostream>using namespace std;const int MAX=34;int map[MAX][MAX];int row;void input(){ char temp;for(int i=0;i<row;i++){ for(int j=0;j<row;j++) { cin>>temp; map[i][j]=temp-'0'; }}}__int64 dp() //动态规划 { __int64 num[MAX][MAX]={1}; for(int i=0;i<row;i++) { for(int j=0;j<row;j++) { if(map[i][j]==0 || num[i][j]==0) continue; if(i+map[i][j]<row) num[i+map[i][j]][j]+=num[i][j]; if(j+map[i][j]<row) num[i][j+map[i][j]]+=num[i][j]; } } return num[row-1][row-1];}int main(){ while(cin>>row,row!=-1) { input(); cout<<dp()<<endl; } return 0;}
2、记忆化搜索：
#include<iostream>using namespace std;const int dir[2][2]={{0,1},{1,0}};const int MAX=35; int map[MAX][MAX];__int64 DP[MAX][MAX];bool visit[MAX][MAX];int n;__int64 DFS(int x,int y) //记忆化搜索 { if(visit[x][y]==true) return DP[x][y]; visit[x][y]=true; for(int i=0;i<2;i++) { int xx=x+dir[i][0]*map[x][y]; int yy=y+dir[i][1]*map[x][y]; if(xx>=1&&xx<=n&&yy>=1&&yy<=n) { DP[x][y]=DP[x][y]+DFS(xx,yy); } } return DP[x][y];}void input(){ char c; for(int i=1;i<=n;i++) { getchar(); for(int j=1;j<=n;j++) { scanf("%c",&c); map[i][j]=c-'0'; } }} int main(){ while(scanf("%d",&n)!=EOF,n!=-1) { input(); memset(DP,0,sizeof(DP)); memset(visit,false,sizeof(visit)); DP[n][n]=1; visit[n][n]=true; printf("%I64d\n",DFS(1,1)); } return 0;}