2010年8月16日
#include <stdio.h>
#define N 2001
#define inf 10000000
#define max(a,b) ((a)>(b)?(a):(b))
int f[N][N],q[N],id[N];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int t,n,maxp,w,ap,bp,as,bs;
scanf("%d",&t);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(t--) {
scanf("%d%d%d",&n,&maxp,&w);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=0;i<n;++i) {
scanf("%d%d%d%d",&ap,&bp,&as,&bs);
for(int j=0;j<=maxp;++j)f[i][j]=-inf;
if(i<=w)for(int j=0;j<=as;++j)f[i][j]=-ap*j;
if(i>0)for(int j=0;j<=maxp;++j)f[i][j]=max(f[i][j],f[i-1][j]);
if (i==0||i<=w) continue;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int j=0,l=0,r=-1;j<=maxp;++j) {
int tmp=f[i-w-1][j]+j*ap;
while(l<=r&&q[r]<tmp)--r;
q[++r]=tmp,id[r]=j;
while(l<=r&&id[l]+as<j)++l;
f[i][j]=max(f[i][j],q[l]-j*ap);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int j=maxp,l=0,r=-1;j>=0;--j) {
int tmp=f[i-w-1][j]+j*bp;
while(l<=r&&q[r]<tmp)--r;
q[++r]=tmp,id[r]=j;
while(l<=r&&id[l]-bs>j)++l;
f[i][j]=max(f[i][j],q[l]-j*bp);
}
}
int ans=0;
for(int i=0;i<=maxp;++i)ans=max(ans,f[n-1][i]);
printf("%d\n",ans);
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
2010年8月9日
#include <stdio.h> using namespace std; #define N 100010 #define max(x,y) ((x)>(y)?(x):(y)) typedef long long LL; int s[N]; struct point { int x, y; point(){} point(int x,int y):x(x),y(y){} }p[N]; point operator - (const point &a, const point &b) { return point(a.x-b.x, a.y-b.y); } LL operator ^ (const point &a, const point &b) { return (LL)a.x*b.y - (LL)a.y*b.x; } inline int get(){ int s=0; char c; while(c=getchar(),c!=' '&&c!='\n')s=s*10+c-'0'; return s; } int main() { int n,k; s[0]=0; while (~scanf("%d ",&n)){ k=get();n++; for(int i=1;i<n;++i){ s[i]=get(); s[i]+=s[i-1]; } double ans=0; for(int i=k,m=-1,f=0;i<n;++i){ point now(i-k,s[i-k]); while(f<m&&(p[m]-p[m-1]^now-p[m-1])<0)--m; p[++m]=now; while(f<m&&(LL)(s[i]-p[f].y)*(i-p[f+1].x)<(LL)(s[i]-p[f+1].y)*(i-p[f].x))f++; ans=max(ans,double(s[i]-p[f].y)/(i-p[f].x)); } printf("%.2lf\n",ans); } }
2010年8月1日
摘要: #include <stdio.h>#include <math.h>#include <algorithm>using namespace std;const double eps=1e-8;int so,mo,br;inline int dcmp(double... 阅读全文
2010年7月27日
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
const double eps=1e-8;
double h,ans,cake;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct point {
double x,y;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) point () {}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) point (double x,double y):x(x),y(y) {}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) void get() {scanf("%lf%lf",&x,&y);}
};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct poly {
point p[21];
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) void get() {for(int i=0;i<n;i++)p[i].get();p[n]=p[0];}
}sg;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int dcmp(double x) {
return (x>eps)-(x<-eps);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) double cross(point o,point p,point q) {
return (p.x-o.x)*(q.y-o.y)-(p.y-o.y)*(q.x-o.x);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) point lineinter(point a,point b,point c,point d) {
double u=cross(a,b,c),v=cross(b,a,d);
return point((c.x*v+d.x*u)/(u+v),(c.y*v+d.y*u)/(u+v));
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) double dis(point a,point b) {
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void push(point a,point b,point &c,point &d) {
double x=a.y-b.y,y=b.x-a.x,t=h/dis(a,b);
c=point(a.x+x*t,a.y+y*t);
d=point(b.x+x*t,b.y+y*t);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void cut(point a,point b,poly tg,poly &g) {
push(a,b,a,b);
g.n=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=0;i<tg.n;i++) {
int u=dcmp(cross(a,b,tg.p[i])),v=dcmp(cross(a,b,tg.p[i+1]));
if(u>=0)g.p[g.n++]=tg.p[i];
if(u*v<0) g.p[g.n++]=lineinter(a,b,tg.p[i],tg.p[i+1]);
}
g.p[g.n]=g.p[0];
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) double area(poly g) {
double sum=0;
for(int i=2;i<g.n;i++)
sum+=cross(g.p[0],g.p[i-1],g.p[i]);
return 0.5*sum;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void dfs(int i,int step,poly g) {
if(step+i<sg.n)dfs(i+1,step,g);
cut(sg.p[i],sg.p[i+1],g,g);
if(step==1)ans=max(ans,cake-area(g));
else dfs(i+1,step-1,g);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int k;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(scanf("%d%d%lf",&sg.n,&k,&h),sg.n||k||h) {
sg.get();
cake=area(sg);
ans=0;
k=min(k,sg.n);
if(k&&h)dfs(0,k,sg);
printf("%.2lf\n",ans);
}
return 0;
}
2010年7月23日
#include <stdio.h> #include <math.h> #define max(a,b) (a>b?a:b) int n;
struct seg { double l, r, t; } a[50];
int main() { while (scanf("%d", &n), n) { for (int i = 0; i < n; i++) { scanf("%lf", &a[i].t); a[i].l = 0.0; for (int j = 0; j < i; j++) a[i].l = max(a[i].l, a[j].r - fabs(a[i].t - a[j].t) / 2); a[i].r = a[i].l + a[i].t; } for (int i = 1; i < n; i++) for (int j = 0; j < i; j++) if (a[i].l < a[i].r) { if (a[i].t > a[j].t && a[i].l < a[j].r) a[j].r = a[i].l; else if (a[i].t < a[j].t && a[j].r > a[i].l) a[i].l = a[j].r; } for (int i = 0; i < n; i++) if (a[i].l < a[i].r)printf("%d ", i + 1); puts(""); } }
2010年7月16日
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct point {
int x,y;
}p[100010];
int c[100010],n,d,a[100010],map[100010],t;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) bool cmp(point p0,point p1) {
return p0.x<p1.x;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int lowbit(int x) {
return x&(-x);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int sum(int x) {
int s=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(x) {
s=(s+c[x])%9901;
x-=lowbit(x);
}
return s;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int update(int x,int y) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(x<=n) {
c[x]=(c[x]+y)%9901;
x+=lowbit(x);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int find(int x,bool y) {
int l=1,r=n,m,ans=-1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(y) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(l<=r) {
m=(l+r)>>1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(p[m].x>=x) {
ans=m;
r=m-1;
}
else l=m+1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(l<=r) {
m=(l+r)>>1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(p[m].x<=x) {
ans=m;
l=m+1;
}
else r=m-1;
}
}
return ans;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(scanf("%d%d",&n,&d)!=EOF) {
memset(c,0,sizeof(c[0])*(n+1));
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
p[i].x=a[i];
p[i].y=i;
}
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;i++)map[p[i].y]=i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=1;i<=n;i++) {
int l=find(a[i]-d,1),r=find(a[i]+d,0);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(l+1&&r+1&&l<=r) {
t=(9901+sum(r)-sum(l-1)+1)%9901;//+1巧妙之处,用于标记是否被更新,答案再减去n即可
update(map[i],t);
}
}
printf("%d\n",(9901*20+sum(n)-n)%9901);
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
2010年7月15日
#include <stdio.h>
#include <algorithm>
using namespace std;
int cas,tim,n,x,y,a[60],b[60],f[210];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
scanf("%d",&cas);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int tim=0;tim<cas;) {
scanf("%d%d%d",&n,&x,&y);
for(int i=1;i<=n;i++)//下标重1开始
scanf("%d%d",&a[i],&b[i]);
int l=0,r=a[1]*x+b[1]*y,m;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(l<=r) {
m=(l+r)>>1;
for(int i=1;i<=x;i++)f[i]=-999999999;
f[0]=0;
for(int i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int v=x;v>=0;v--) {
f[v]+=m/b[i];//新入工人要更新
for(int j=0;j<v;j++) if (m>=(v-j)*a[i])
f[v]=max(f[v],f[j]+(m-a[i]*(v-j))/b[i]);
}
if(f[x]>=y)r=m-1;//最左逼近
else l=m+1;
}
printf("Case %d: %d\n",++tim,l);
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
2010年7月14日
摘要: #include <stdio.h>#include <algorithm>#include <math.h>#define zero(x) if(dcmp(x)==0)x=0#define cross(p0,p1,p2) ((p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y... 阅读全文
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define lowbit(x) (x&(-x))
bool c[1010][1010];
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) bool sum(int x,int y) {
bool s=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(x) {
int yy=y;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(yy) {
s^=c[x][yy];
yy-=lowbit(yy);
}
x-=lowbit(x);
}
return s;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void update(int x,int y) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(x<=n) {
int yy=y;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(yy<=n) {
c[x][yy]=!c[x][yy];
yy+=lowbit(yy);
}
x+=lowbit(x);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int t,x,y,xx,yy,m;
char s[2];
scanf("%d",&t);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(t--) {
memset(c,0,sizeof(c));
scanf("%d%d",&n,&m);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(m--) {
scanf("%s",s);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(s[0]=='C') {
scanf("%d%d%d%d",&x,&y,&xx,&yy);
update(++xx,++yy);
update(x,yy);
update(xx,y);
update(x,y);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
scanf("%d%d",&x,&y);
printf("%d\n",sum(x,y));
}
}
puts("");
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
2010年6月21日
//搜索入门
#include <stdio.h>
#include <algorithm>
using namespace std;
int length,a[64],n,sum;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) bool ok,v[64]= {0};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void dfs(int i,int size,int step) {
if(size==length)i=0,size=0,step--;
if(step==0)ok=1;
for(int old=-1;!ok&&i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(!v[i]&&a[i]!=old&&(size+a[i])<=length) {
v[i]=1;
old=a[i];
dfs(i+1,size+a[i],step);
v[i]=0;
if(size==0)return;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) bool cmp(int x,int y) {return x>y;}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(scanf("%d",&n),n) {
sum=0,ok=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=0;i<n;i++) {scanf("%d",&a[i]);sum+=a[i];}
sort(a,a+n,cmp);
for(length=a[0];!ok&&length<=sum;length++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(sum%length==0) {
dfs(0,0,(sum/length)-1);
if(ok)printf("%d\n",length);
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|
|
CALENDER
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 1 | 2 | 3 | 4 | 5 |
|
常用链接
留言簿
随笔分类
随笔档案
搜索
最新随笔
最新评论
![](/images/xml.gif)
Powered By: 博客园 模板提供:沪江博客
|