21/7/2012 ICPC培训 第六天
今天本来安排刷DP的，可是各种不懂呀！！！勉强刷出两道题！
眼看没做出题，还是刷两道二分查找吧。
其他的就是讲解了昨天下午的比赛题目。各种思路，搞得我甚是膜拜。每种思路都很简洁，
把需要解决的问题抽象的很好很好。为啥我就不能想出来呢？？？无语吆。。。
不过膜拜归膜拜，有了思路得在这两天把没做出来的几题刷了。
最后，晚上，张浩然同学给我们简单介绍了下STL。
还是来讲讲我做的题吧。
第一题（HDU1881）
这题是01背包的变形。思路和01背包很像。
我搞不明白为什么要先对各个bg按照离校时间由小到大排序，然后再用01背包的方法解决？
期待，看到博文的大神赐教哇。。。
代码：
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;const int MAX=31;int dp[MAX*MAX*2];int maxTime,n;struct node{ int h,l,t; bool operator < (const node &tmp) const { return t<tmp.t; } }temp[MAX];//bool cmp(node a,node b)//{// return a.t<b.t;//}void input(){ maxTime=0; for(int i=0;i<n;i++) { cin>>temp[i].h>>temp[i].l>>temp[i].t; maxTime=maxTime>temp[i].t?maxTime:temp[i].t; }}void pack(){ memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) { for(int j=maxTime;j>=temp[i].l;j--) { if(temp[i].t>=j && dp[j]<dp[j-temp[i].l]+temp[i].h) { dp[j]=dp[j-temp[i].l]+temp[i].h; } } } int result=-1; for(int k=0;k<=maxTime;k++) { result=result>dp[k]?result:dp[k]; } cout<<result<<endl; } int main(){ while(cin>>n,n>=0) { input(); //sort(temp,temp+n,cmp); sort(temp,temp+n); pack(); } return 0;}
第二题（HDU2141）
看到这类题，爆搜很通用，前提是数据量不太大。这题显然爆搜超时。
如何优化呢？可以对C二分，也可以对A+B二分。对A+B二分时间性能更好点。
代码：
#include<iostream>#include<cstring>#include<algorithm> using namespace std;const int MAX=500;int a,b,c,quary,ans,cas=1;int A[MAX],B[MAX],C[MAX],D[MAX*MAX];bool flag; void input(){ int i; for(i=0;i<a;i++) { scanf("%d",&A[i]); } for(i=0;i<b;i++) { scanf("%d",&B[i]); } for(i=0;i<c;i++) { scanf("%d",&C[i]); }}void preDeal(){ int k=0; for(int i=0;i<a;i++) { for(int j=0;j<b;j++) { D[k++]=A[i]+B[j]; } } sort(D,D+k); }void binSearch(int low,int high){ int mid=(low+high)/2; if(low+1==high && D[mid]!=ans) return; if(D[mid]==ans) { flag=true; return; } else if(D[mid]<ans) { binSearch(mid,high); } else { binSearch(low,mid); }} void deal(){ scanf("%d",&quary); printf("Case %d:\n",cas++); int temp,i,j; for(i=0;i<quary;i++) { scanf("%d",&temp); flag=false; for(j=0;j<c;j++) { if(flag) break; ans=temp-C[j]; binSearch(0,a*b-1); } if(flag) printf("YES\n"); else printf("NO\n"); }} int main(){ while(cin>>a>>b>>c) { input(); preDeal(); deal(); } return 0;}
第三题（HDU2199）
这题是解方程。
这个方程在0—100范围内明显是递增的。所以，输入的y太大或太小就可以直接判断是No soulution!了。
另外，这题不能1Y的原因在于你选择的精度大小。刚开始我用的精度是1e-7，结果就TLE了。然后改成
1e-5，0MS过了。
代码：
#include<iostream>#include<iomanip> #include<cmath>using namespace std;const double accurate=1e-5; //这里精度写成1e-7，TLE了 double x,y; double calculate(double x){ return 8*pow(x,4) + 7*pow(x,3) + 2*pow(x,2) + 3*x + 6 ;}void binSearch(double low,double high){ double mid=(low+high)*1.0/2.0; if(fabs(calculate(mid)-y)<=accurate) { x=mid; return; } else if(calculate(mid)<y) { binSearch(mid,high); } else { binSearch(low,mid); }} int main(){ int cas; scanf("%d",&cas); while(cas--) { scanf("%lf",&y); if(y<6 || y>807020306) { printf("No solution!\n"); continue; } binSearch(0,100); cout<<setiosflags(ios::fixed)<<setprecision(4)<<x<<endl; } return 0;}
最后一题是昨天下午比赛的一道DP题，在同学的帮助下找到状态转移方程了！
然后晚上出题的同学又讲了一种完全不同构造方程的思路。可见的是DP借助数组来表达状态，
你给数组赋予不同的含义也就可以找到不同大方程。
DP很抽象，得加强练习了。。。