2010年8月16日

hdu 3401 Trade

#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];

int main(){

int t,n,maxp,w,ap,bp,as,bs;

scanf("%d",&t);

while(t--){

scanf("%d%d%d",&n,&maxp,&w);

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;

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);

}

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;

}

posted @ 2010-08-16 21:40 huicpc0860 閱讀(514) | 評論 (1) | 編輯收藏

2010年8月9日

hdu 2993 MAX Average Problem

#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);
    }
}

posted @ 2010-08-09 20:24 huicpc0860 閱讀(892) | 評論 (0) | 編輯收藏

2010年8月1日

poj 1133 stars

摘要: #include <stdio.h>#include <math.h>#include <algorithm>using namespace std;const double eps=1e-8;int so,mo,br;inline int dcmp(double... 閱讀全文

posted @ 2010-08-01 20:05 huicpc0860 閱讀(352) | 評論 (0) | 編輯收藏

2010年7月27日

poj 1271 Nice Milk

#include <stdio.h>

#include <math.h>

#include <algorithm>

using namespace std;

const double eps=1e-8;

double h,ans,cake;

struct point {

double x,y;

point (){}

point (double x,double y):x(x),y(y){}

void get(){scanf("%lf%lf",&x,&y);}

};

struct poly{

point p[21];

int n;

void get(){for(int i=0;i<n;i++)p[i].get();p[n]=p[0];}

}sg;

int dcmp(double x){

return (x>eps)-(x<-eps);

}

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);

}

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));

}

double dis(point a,point b){

return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

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);

}

void cut(point a,point b,poly tg,poly &g){

push(a,b,a,b);

g.n=0;

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];

}

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;

}

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);

}

int main(){

int k;

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;

}

posted @ 2010-07-27 18:46 huicpc0860 閱讀(327) | 評論 (0) | 編輯收藏

2010年7月23日

poj 3347 Kadj Squares

#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("");
    }
}

posted @ 2010-07-23 18:51 huicpc0860 閱讀(219) | 評論 (0) | 編輯收藏

2010年7月16日

bupt 1849 Counting Sequences

#include <stdio.h>

#include <algorithm>

#include <string.h>

using namespace std;

struct point{

int x,y;

}p[100010];

int c[100010],n,d,a[100010],map[100010],t;

bool cmp(point p0,point p1){

return p0.x<p1.x;

}

int lowbit(int x){

return x&(-x);

}

int sum(int x){

int s=0;

while(x){

s=(s+c[x])%9901;

x-=lowbit(x);

}

return s;

}

int update(int x,int y){

while(x<=n){

c[x]=(c[x]+y)%9901;

x+=lowbit(x);

}

int find(int x,bool y){

int l=1,r=n,m,ans=-1;

if(y){

while(l<=r){

m=(l+r)>>1;

if(p[m].x>=x){

ans=m;

r=m-1;

}

else l=m+1;

}

}else{

while(l<=r){

m=(l+r)>>1;

if(p[m].x<=x){

ans=m;

l=m+1;

}

else r=m-1;

}

return ans;

}

int main(){

while(scanf("%d%d",&n,&d)!=EOF){

memset(c,0,sizeof(c[0])*(n+1));

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;

for(int i=1;i<=n;i++){

int l=find(a[i]-d,1),r=find(a[i]+d,0);

if(l+1&&r+1&&l<=r){

t=(9901+sum(r)-sum(l-1)+1)%9901;//+1巧妙之處，用于標(biāo)記是否被更新，答案再減去n即可

update(map[i],t);

}

printf("%d\n",(9901*20+sum(n)-n)%9901);

}

return 0;

}

posted @ 2010-07-16 18:06 huicpc0860 閱讀(249) | 評論 (0) | 編輯收藏

2010年7月15日

hdu 3433 A Task Process

#include <stdio.h>

#include <algorithm>

using namespace std;

int cas,tim,n,x,y,a[60],b[60],f[210];

int main(){

scanf("%d",&cas);

for(int tim=0;tim<cas;){

scanf("%d%d%d",&n,&x,&y);

for(int i=1;i<=n;i++)//下標(biāo)重1開始

scanf("%d%d",&a[i],&b[i]);

int l=0,r=a[1]*x+b[1]*y,m;

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++)

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;

}

posted @ 2010-07-15 20:26 huicpc0860 閱讀(419) | 評論 (0) | 編輯收藏

2010年7月14日

hdu 3437 Garden

摘要: #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... 閱讀全文

posted @ 2010-07-14 21:39 huicpc0860 閱讀(306) | 評論 (0) | 編輯收藏

poj 2155 Matrix

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define lowbit(x) (x&(-x))

bool c[1010][1010];

int n;

bool sum(int x,int y){

bool s=0;

while(x){

int yy=y;

while(yy){

s^=c[x][yy];

yy-=lowbit(yy);

}

x-=lowbit(x);

}

return s;

}

void update(int x,int y){

while(x<=n){

int yy=y;

while(yy<=n){

c[x][yy]=!c[x][yy];

yy+=lowbit(yy);

}

x+=lowbit(x);

}

int main(){

int t,x,y,xx,yy,m;

char s[2];

scanf("%d",&t);

while(t--){

memset(c,0,sizeof(c));

scanf("%d%d",&n,&m);

while(m--){

scanf("%s",s);

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);

}else{

scanf("%d%d",&x,&y);

printf("%d\n",sum(x,y));

}

puts("");

}

return 0;

}

posted @ 2010-07-14 12:47 huicpc0860 閱讀(148) | 評論 (0) | 編輯收藏

2010年6月21日

poj 1011 Sticks

//搜索入門

#include <stdio.h>

#include <algorithm>

using namespace std;

int length,a[64],n,sum;

bool ok,v[64]={0};

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++)

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;

}

bool cmp(int x,int y){return x>y;}

int main(){

while(scanf("%d",&n),n){

sum=0,ok=0;

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++)

if(sum%length==0){

dfs(0,0,(sum/length)-1);

if(ok)printf("%d\n",length);

}

return 0;

}

posted @ 2010-06-21 22:38 huicpc0860 閱讀(244) | 評論 (0) | 編輯收藏

僅列出標(biāo)題下一頁

CALENDER

2025年7月

日

一

二

三

四

五

六

2010年8月16日

2010年8月9日

2010年8月1日

2010年7月27日

2010年7月23日

2010年7月16日

2010年7月15日

2010年7月14日

2010年6月21日

常用鏈接

留言簿

隨筆分類

隨筆檔案

搜索

最新隨筆

最新評論