链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1166
#include "iostream"
#include "cstring"
using namespace std;
struct segment_tree
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int left,right,num;
}tree[150010];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int a[50010];
int T,n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Build(int left,int right,int i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
tree[i].left=left;
tree[i].right=right;
if(left==right)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tree[i].num=a[left];
return;
}
int mid=(left+right)/2;
Build(left,mid,2*i);
Build(mid+1,right,2*i+1);
tree[i].num=tree[2*i].num+tree[2*i+1].num;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Updata(int id,int num,int i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(tree[i].left==tree[i].right)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tree[i].num+=num;
return;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tree[i].num+=num;
if(id<=tree[i*2].right) Updata(id,num,i*2);
else Updata(id,num,i*2+1);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int Query(int left,int right,int i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(tree[i].left==left&&tree[i].right==right) return tree[i].num;
int mid=(tree[i].left+tree[i].right)/2;
if(right<=mid) return Query(left,right,i*2);
else if(left>mid) return Query(left,right,i*2+1);
else return Query(left,mid,i*2)+Query(mid+1,right,i*2+1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,t1,t2;
char s[10];
scanf("%d",&T);
for(int k=1;k<=T;k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
Build(1,n,1);
printf("Case %d:\n",k);
while(1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%s",s);
if(strcmp(s,"End")==0) break;
scanf("%d%d",&t1,&t2);
if(strcmp(s,"Query")==0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int ans=Query(t1,t2,1);
printf("%d\n",ans);
}
if(strcmp(s,"Sub")==0) Updata(t1,-t2,1);
if(strcmp(s,"Add")==0) Updata(t1,t2,1);
}
}
return 0;
}
posted @
2010-11-14 12:45 wuxu 阅读(273) |
评论 (0) |
编辑 收藏
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1042
这道题是大数和普通数的乘法,步骤如下:
1、判断乘后大数的位数,此题约为40000;
2、选择由那种类型数组存储,一般由int存储,一个数能存5位(10000*100000<2^31);
3、确定数组长度,此题约为40000/5=8000;
4、计算数组中每个数与普通数的乘积并存入数组;
5、计算数组中每个数乘普通数的进位,加入高一位数组;
6、输出时先计算使用了多少个的数组,然后向前输出数组。
#include<iostream>
using namespace std;
int a[8001],n;
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
while(scanf("%d",&n)!=EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int i,j;
memset(a,0,sizeof(a));
for(i=2,a[0]=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j=0;j<8000;j++) a[j]*=i;
for(j=0;j<8000;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
a[j+1]+=a[j]/100000;
a[j]%=100000;
}
}
for(i=8000;i>=0&&!a[i];i--);
printf("%d",a[i--]);
for(;i>=0;i--) printf("%05d",a[i]);
printf("\n");
}
return 0;
}
posted @
2010-10-31 14:32 wuxu 阅读(2283) |
评论 (2) |
编辑 收藏
posted @
2010-09-22 12:12 wuxu 阅读(224) |
评论 (0) |
编辑 收藏
题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1609
方法一:转化为求一维最长上升子序列。O(nlogn)
#include<iostream>
#include<algorithm>
using namespace std;
int b[10005];
int n;
typedef struct node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int l,m;
bool operator<(node t)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(l<t.l) return 1;
else if(l==t.l&&m<t.m) return 1;
else return 0;
}
}block;
block a[10005];
int LIS()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int L=0;
for(int i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int ll=1,rr=L;
while(ll<=rr)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int mid=(ll+rr)/2;
if(b[mid]<=a[i].m) ll=mid+1;
else rr=mid-1;
}
b[ll]=a[i].m;
if(ll>L) L++;
}
return L;
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
while(scanf("%d",&n)!=EOF&&n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].l,&a[i].m);
sort(a+1,a+n+1);
printf("%d\n",LIS());
}
printf("*\n");
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
方法二:状态转移方程为:f[i][j]=max{f[i-1][j],f[i][j-1]}+a[i][j].
#include<iostream>
using namespace std;
#define max(x,y) (x>y?x:y)
int a[105][105],f[105][105];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int n;
while(scanf("%d",&n)!=EOF&&n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int i,j,k,s;
memset(a,0,sizeof(a));
memset(f,-1,sizeof(f));
f[0][0]=0;
f[0][1]=0;
f[1][0]=0;
int xx=0,yy=0;
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d%d",&k,&s);
if(xx<k) xx=k;
if(yy<s) yy=s;
a[k][s]++;
}
for(i=1;i<=xx;i++)
for(j=1;j<=yy;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(f[i-1][j]!=-1)
f[i][j]=max(f[i][j],f[i-1][j]+a[i][j]);
if(f[i][j-1]!=-1)
f[i][j]=max(f[i][j],f[i][j-1]+a[i][j]);
}
int ans=0;
for(i=1;i<=xx;i++)
for(j=1;j<=yy;j++)
if(ans<f[i][j]) ans=f[i][j];
printf("%d\n",ans);
}
printf("*\n");
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-09-07 21:08 wuxu 阅读(636) |
评论 (0) |
编辑 收藏
O(n^2)代码:
#include<iostream>
using namespace std;
int h[40000],d[40000];
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int test=0;
while(1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int i,j,k;
test++;
scanf("%d",&h[1]);
if(h[1]==-1) break;
k=1;
while(scanf("%d",&j)!=EOF&&j!=-1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
h[++k]=j;
}
h[0]=40000;
memset(d,0,sizeof(d));
for(i=1;i<=k;i++)
for(j=0;j<i;j++)
if(h[j]>h[i]&&d[j]+1>d[i])
d[i]=d[j]+1;
int ans=0;
for(i=1;i<=k;i++)
if(d[i]>ans) ans=d[i];
if(test!=1) printf("\n");
printf("Test #%d:\n",test);
printf(" maximum possible interceptions: %d\n",ans);
}
//system("pause");
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
O(nlogn)代码:
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*============================*\
最长下降子序列 O(nlogn)
\*============================*/
#include<iostream>
using namespace std;
const int inf=1000000;
int a[30000],b[30000];//b[i]表示长度为i的下降序列中,末尾数最大的那个序列的代表。
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int lds()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int ans=0;
b[0]=inf;
for(int i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int l=1,r=ans;
while(l<=r) //找l最小的b[l],使b[l]<=a[i].
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int t=(l+r)/2;
if(b[t]>a[i]) l=t+1;
else r=t-1;
}
b[l]=a[i];
if(l>ans) ans++;
}
return ans;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int test=0;
while(scanf("%d",&a[1])!=EOF&&a[1]!=-1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int i,t;
n=1;
test++;
while(scanf("%d",&t)!=EOF&&t!=-1)
a[++n]=t;
if(test!=1) printf("\n");
printf("Test #%d:\n",test);
printf(" maximum possible interceptions: %d\n",lds());
}
//system("pause");
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-09-06 20:05 wuxu 阅读(384) |
评论 (0) |
编辑 收藏
题目链接:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4007很好的一道题目,用f[i,j]表示前i个学生分为j个班时的最小unhappy值,状态转移方程为:f[i,j]=min{f[k,j-1],+(sum[i]-sum[k])*g[j]}.其中a<=i-k<=b,sum[i] = sigma {(x[s] -L)^2 | s≤ i}.
但现在的时间复杂度为O(k*n^2),显然会TLE。将转移方程整理一下:f[i,j]=sum[i]*g[j]+min{f[k,j-1]-sum[k]*g[j]}. 显然可维护一个单调递增队列,每次转移之前将新的可选状态从队列尾插入,同时保证队列头的元素在可选范围之内。这样每次转移就可以只取队列头的元素,总的时间复杂度为O(n*k).
#include<iostream>
using namespace std;
const long long inf=100000000000000ll;
long long sum[10005],aver;
long long f[10005][205];
int x[10005],g[205];
int n,m,a,b;
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
long long unhap;
int loc;
}node;
node q[10005];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int test=0;
while(scanf("%d%d%d%d",&n,&m,&a,&b)!=EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
test++;
aver=0;
int i,j;
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d",&x[i]);
aver+=x[i];
}
aver/=n;
for(i=1;i<=m;i++)
scanf("%d",&g[i]);
sum[0]=0;
for(i=1;i<=n;i++)
sum[i]=sum[i-1]+(x[i]-aver)*(x[i]-aver);
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
f[i][j]=inf;
f[0][0]=0;
long long ans_unhap=inf;
int ans_k=m+1,ans_t=n+1;
for(j=1;j<=m;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int head=0,tail=0;
for(i=a;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
node temp;
if(f[i-a][j-1]!=inf)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
temp.unhap=f[i-a][j-1]-sum[i-a]*g[j];
temp.loc=i-a;
while(head<tail&&q[tail-1].unhap>=temp.unhap) tail--; //用>=是为了保证最后一个班的学生在多解的情况下人数最少。
q[tail].unhap=temp.unhap;
q[tail++].loc=temp.loc;
}
while(head<tail&&q[head].loc<i-b) head++;
if(head<tail) f[i][j]=q[head].unhap+sum[i]*g[j];
}
if(f[n][j]!=inf) //求多解情况下的最小分班数。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(ans_unhap>f[n][j])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ans_unhap=f[n][j];
ans_k=j;
ans_t=n-q[head].loc;
}
}
}
if(test!=1) printf("\n");
if(ans_unhap==inf) printf("No solution.\n");
else printf("%lld %d %d",ans_unhap,ans_k,ans_t);
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-09-04 22:40 wuxu 阅读(363) |
评论 (0) |
编辑 收藏
简单DP 题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=3127![](http://www.cppblog.com/images/cppblog_com/wuxu/eeeee.png)
状态转移方程:f[i,j]=max{f[i,j],f[i-a,j]+f[a,j-b]+p,f[i,j-b]+f[i-a,b]+p}
f[i,j]=max{f[i,j],f[i-b,j]+f[b,j-a]+p,f[i,j-a]+f[i-b,a]+p}
#include<iostream>
#include<algorithm>
#define max(a,b) (a>b?a:b)
using namespace std;
int test,n,x,y;
int f[1005][1005];
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int len,wth,val;
}CLOTH;
CLOTH c[15];
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
scanf("%d",&test);
while(test--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d%d%d",&n,&x,&y);
for(int i=0;i<n;i++)
scanf("%d%d%d",&c[i].len,&c[i].wth,&c[i].val);
memset(f,0,sizeof(f));
for(int i=1;i<=x;i++)
for(int j=1;j<=y;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(int k=0;k<n;k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int a=c[k].len;
int b=c[k].wth;
if(i>=a&&j>=b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
f[i][j]=max(f[i][j],f[i-a][j]+f[a][j-b]+c[k].val);
f[i][j]=max(f[i][j],f[i][j-b]+f[i-a][b]+c[k].val);
}
swap(a,b);
if(i>=a&&j>=b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
f[i][j]=max(f[i][j],f[i-a][j]+f[a][j-b]+c[k].val);
f[i][j]=max(f[i][j],f[i][j-b]+f[i-a][b]+c[k].val);
}
}
}
printf("%d\n",f[x][y]);
}
//system("pause");
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-08-29 10:38 wuxu 阅读(282) |
评论 (0) |
编辑 收藏
RMQ(Range Minimum/Maximum Query)问题是求区间最值问题,用ST算法,可以做到O(nlogn)的预处理,O(1)地回答每个询问。
以求最大值为例,设f[i,j]表示以i为起点,长度为2^j这个区间中的最大值,即[i,i+2^j-1]这个区间内的最大值,那么在询问[a,b]区间的最大值时答案就是max(f[a,k], f[b-2^k+1,k]),其中k是满足2^k<=b-a的最大的k,即k=ln(b-a+1)/ln(2);另外,这两个区间必须覆盖[a,b].
f的求法可以用动态规划,f[i,j]=max(f[i,j-1],f[i+2^(j-1),j-1]).
题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=3264
#include<iostream>
#include<cmath>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
int n,q,a,b;
int h[50005];
int maxn[50005][16];
int minn[50005][16];
void st_init()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
for(int i=1;i<=n;i++)
maxn[i][0]=minn[i][0]=h[i];
int m=int(log(double(n))/log(2.0));
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
maxn[j][i]=maxn[j][i-1];
if(j+(1<<(i-1))<=n)
maxn[j][i]=max(maxn[j][i],maxn[j+(1<<(i-1))][i-1]);
}
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
minn[j][i]=minn[j][i-1];
if(j+(1<<(i-1))<=n)
minn[j][i]=min(minn[j][i],minn[j+(1<<(i-1))][i-1]);
}
}
int st_search(int l,int r)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int m=int(log(double(r-l+1))/log(2.0));
int mx=max(maxn[l][m],maxn[r-(1<<m)+1][m]);
int mn=min(minn[l][m],minn[r-(1<<m)+1][m]);
return mx-mn;
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
scanf("%d",&h[i]);
st_init();
for(int i=1;i<=q;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d%d",&a,&b);
printf("%d\n",st_search(a,b));
}
//system("pause");
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-08-28 13:29 wuxu 阅读(197) |
评论 (0) |
编辑 收藏
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=3401用f[i][j]表示第i天股票数为j的最大收益,f[i][j]可以从以下三个地方得到:
1、在上次交易的基础上再买一些: f[i][j]=max{f[i][j],f[r][k]-(j-k)*b_price[i]} 0<r<i-w, 0<=j-k<=b_num[i]
2、在上次交易的基础上卖出一些: f[i][j]=max{f[i][j],f[r][k]+(k-j)*s_price[i]} 0<r<i-w, 0<=k-j<=s_num[i]
3、当天股票不动: f[i][j]=max{f[i][j],f[i-1][j]}
这样的时间复杂度为O(T^2*MaxP^2),需要做一些优化.
对于买股票的时候,f[r][k]-(j-k)*b_price[i]=f[r][k]+k*b_price[i]-j*b_price[i] ,(j>= k>=j-b_num[i]),f[i][j]的最优值由f[r][k]+k*b_price[i]确定,由递推方程可知,f[r][k]始终是股票数为k的最大值. 对于某个j,f[r][k]+k*b_price[i]已经重复求过了,这次只需要求f[r][j]+j*b_price[i]即可,因此可以用单调队列来保存这些信息,并且可以方便的取出最大值。 卖股票的情况也同上面类似。此时的时间复杂度为O(T*MaxT).
#include<iostream>
#define max(a,b) (a>b?a:b)
using namespace std;
const int inf=0x7fffffff;
int test,t,maxp,w;
int b_price[2005],s_price[2005];
int b_num[2005],s_num[2005];
int f[2005][2005];
typedef struct node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int mon,num;
}NODE;
NODE q[2005];
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
scanf("%d",&test);
while(test--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d%d%d",&t,&maxp,&w);
for(int i=1;i<=t;i++)
scanf("%d%d%d%d",&b_price[i],&s_price[i],&b_num[i],&s_num[i]);
for(int i=0;i<=t;i++)
for(int j=0;j<=maxp;j++)
f[i][j]=-inf;
for(int i=1;i<=w+1;i++)
for(int j=0;j<=maxp&&j<=b_num[i];j++)
f[i][j]=-j*b_price[i];
for(int i=2;i<=w+1;i++)
for(int j=0;j<=maxp;j++)
f[i][j]=max(f[i-1][j],f[i][j]);
for(int i=w+2;i<=t;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int head=0,tail=0;
for(int j=0;j<=maxp;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
f[i][j]=max(f[i][j],f[i-1][j]);
int pre=i-w-1;
int money=f[pre][j]+j*b_price[i];
while(head<tail&&q[tail-1].mon<money) tail--;
q[tail].mon=money;
q[tail++].num=j;
while(head<tail&&j-q[head].num>b_num[i]) head++;
f[i][j]=max(f[i][j],q[head].mon-j*b_price[i]);
}
head=tail=0;
for(int j=maxp;j>=0;j--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int pre=i-w-1;
int money=f[pre][j]+j*s_price[i];
while(head<tail&&q[tail-1].mon<money) tail--;
q[tail].mon=money;
q[tail++].num=j;
while(head<tail&&q[head].num-j>s_num[i]) head++;
f[i][j]=max(f[i][j],q[head].mon-j*s_price[i]);
}
}
int ans=-inf;
for(int i=0;i<=maxp;i++)
if(f[t][i]>ans) ans=f[t][i];
printf("%d\n",ans);
}
//system("pause");
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-08-27 18:38 wuxu 阅读(574) |
评论 (1) |
编辑 收藏
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=3560题意:求连通分量的个数和环图的个数。如果是环图那么每个点的度数应该为2。
#include<iostream>
using namespace std;
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int v;
int next;
}edge;
edge e[600005];
int head[100005];
int deg[100005];
bool vis[100005];
int n,m,num1,num2;
void bfs(int u)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
num1++;
vis[u]=1;
bool flag=0;
int front=0,rear=0;
int q[100005];
q[rear++]=u;
if(deg[u]!=2) flag=1;
while(front<rear)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int x=q[front++];
for(int i=head[x];i!=-1;i=e[i].next)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(!vis[e[i].v])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
vis[e[i].v]=1;
if(deg[e[i].v]!=2) flag=1;
q[rear++]=e[i].v;
}
}
}
if(!flag) num2++;
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int i,j,uu,vv,tot=0;
memset(head,-1,sizeof(head));
memset(deg,0,sizeof(deg));
memset(vis,0,sizeof(vis));
for(i=0;i<m;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d%d",&uu,&vv);
deg[uu]++;
deg[vv]++;
e[tot].v=vv;
e[tot].next=head[uu];
head[uu]=tot++;
e[tot].v=uu;
e[tot].next=head[vv];
head[vv]=tot++;
}
num1=0,num2=0;
for(i=0;i<n;i++)
if(!vis[i])
bfs(i);
printf("%d %d\n",num1,num2);
}
//system("pause");
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-08-25 18:55 wuxu 阅读(365) |
评论 (2) |
编辑 收藏