题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3415题目大意：给出一个有N个数字（N<=10^5）的环状序列，让你求一个和最大的连续子序列。这个连续子序列的长度小于等于K。
分析：因为序列是环状的，所以可以在序列后面复制前k-1个数字。如果用s[i]来表示复制过后的序列的前i个数的和，那么任意一个子序列[i..j]的和就等于s[j]-s[i-1]。对于每一个j，用s[j]减去最小的一个s[i](i>=j-k)就可以得到以j为终点长度不大于k的和最大的序列了。将原问题转化为这样一个问题后，就可以用单调队列解决了。
单调队列即保持队列中的元素单调递增（或递减）的这样一个队列，可以从两头删除，只能从队尾插入。单调队列的具体作用在于，由于保持队列中的元素满足单调性，对于上述问题中的每个j，可以用O(1)的时间找到对应的s[i]。（保持队列中的元素单调递增的话，队首元素便是所要的元素了）。
维护方法：对于每个j，我们插入s[j-1]的下标，插入时从队尾插入。为了保证队列的单调性，我们从队尾开始删除元素，直到队尾元素对应的值比当前需要插入的s[j-1]小，就将当前元素下标插入到队尾。之所以可以将之前的队列尾部元素全部删除，是因为它们已经不可能成为最优的元素了，因为当前要插入的元素位置比它们靠前，对应的值比它们小。我们要找的，是满足(i>=j-k)的i中最小的s[i]。在插入元素后，从队首开始，将不符合限制条件(i<j-k)的元素全部删除，此时队列一定不为空。（因为刚刚插入了一个一定符合条件的元素）。详细见代码：
#include<iostream>
using namespace std;
const int inf=1000000000;
int sum[200002];
int t,n,k,N;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&N,&k);
sum[0]=0;
for(int i=1;i<=N;i++)
{
scanf("%d",&sum[i]);
sum[i]+=sum[i-1];
}
for(int i=N+1;i<N+k;i++)
sum[i]=sum[N]+sum[i-N];
n=N+k-1;
int start,end,maxn=-inf;
int head=0,tail=0;
int q[200002];
for(int i=1;i<=n;i++)
{
while(head<tail&&sum[i-1]<sum[q[tail-1]]) tail--;
q[tail++]=i-1;
while(head<tail&&i-q[head]>k) head++;
if(maxn<sum[i]-sum[q[head]])
{
maxn=sum[i]-sum[q[head]];
start=q[head]+1;
end=i>N? i-N:i;
}
}
printf("%d %d %d\n",maxn,start,end);
}
//system("pause");
return 0;
}
posted @
2010-08-24 19:59 wuxu 阅读(838) |
评论 (0) |
编辑 收藏
题目链接：
http://acm.pku.edu.cn/JudgeOnline/problem?id=2823
#include<iostream>
using namespace std;
int n,k;
int a[1000002];
void puts_val(int flag)
{
int q[1000002];
int i,head=0,tail=0;
if(flag)
{
for(i=1;i<=k-1;i++)
{
while(head<tail&&a[q[tail-1]]<a[i]) tail--;
q[tail++]=i;
}
for(i=k;i<=n;i++)
{
while(head<tail&&a[q[tail-1]]<a[i]) tail--;
q[tail++]=i;
while(head<tail&&i-q[head]>=k) head++;
if(i!=n) printf("%d ",a[q[head]]);
else printf("%d\n",a[q[head]]);
}
}
else
{
for(i=1;i<=k-1;i++)
{
while(head<tail&&a[q[tail-1]]>a[i]) tail--;
q[tail++]=i;
}
for(i=k;i<=n;i++)
{
while(head<tail&&a[q[tail-1]]>a[i]) tail--;
q[tail++]=i;
while(head<tail&&i-q[head]>=k) head++;
if(i!=n) printf("%d ",a[q[head]]);
else printf("%d\n",a[q[head]]);
}
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
puts_val(0);
puts_val(1);
//system("pause");
return 0;
}
posted @
2010-08-24 17:23 wuxu 阅读(202) |
评论 (0) |
编辑 收藏
经典DP. 题目来源：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1179枚举第一次拿走的边，f[i][j][0]记录i到j的最小值，f[i][j][1]记录最大值，然后递推计算。记录最小值是因为两个负数相乘可能得到一个大的正数。见代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=100000000;
int n,max_score,tot,fir_mov[55];
int f[55][55][2],val[55];
char sign[55][55];
void fun(int a[4],int &tmax,int &tmin)
{
sort(a,a+4);
if(a[0]<tmin) tmin=a[0];
if(a[3]>tmax) tmax=a[3];
}
int main()
{
scanf("%d",&n);
int i,j,k,s;
for(i=0;i<n;i++)
{
getchar();
scanf("%c%d",&sign[(i-1+n)%n][i],&val[i]);
}
int max_score=-inf;
tot=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
for(k=0;k<n;k++)
{
f[j][k][0]=inf; //min
f[j][k][1]=-inf; //max
}
for(j=0;j<n;j++)
{
f[j][j][0]=val[j];
f[j][j][1]=val[j];
}
int start=i,end=(i-1+n)%n;
for(j=1;j<=n-1;j++)
for(k=start;(k+j)%n!=(end+1)%n;k=(k+1)%n)
{
int v=(k+j)%n;
int tmax=-inf,tmin=inf;
for(s=k;s!=v;s=(s+1)%n)
{
if(sign[s][(s+1)%n]=='t')
{
if(tmax<f[k][s][1]+f[(s+1)%n][v][1])
tmax=f[k][s][1]+f[(s+1)%n][v][1];
if(tmin>f[k][s][0]+f[(s+1)%n][v][0])
tmin=f[k][s][0]+f[(s+1)%n][v][0];
}
else
{
int a[4];
a[0]=f[k][s][1]*f[(s+1)%n][v][1];
a[1]=f[k][s][0]*f[(s+1)%n][v][0];
a[2]=f[k][s][0]*f[(s+1)%n][v][1];
a[3]=f[k][s][1]*f[(s+1)%n][v][0];
fun(a,tmax,tmin);
}
}
if(f[k][v][0]>tmin) f[k][v][0]=tmin;
if(f[k][v][1]<tmax) f[k][v][1]=tmax;
}
if(max_score==f[start][end][1])
{
fir_mov[tot++]=i+1;
}
else if(max_score<f[start][end][1])
{
tot=0;
max_score=f[start][end][1];
fir_mov[tot++]=i+1;
}
}
printf("%d\n",max_score);
for(i=0;i<tot;i++)
if(i!=tot-1) printf("%d ",fir_mov[i]);
else printf("%d\n",fir_mov[i]);
//system("pause");
return 0;
}
posted @
2010-08-23 18:36 wuxu 阅读(155) |
评论 (0) |
编辑 收藏
题目来源：
http://acm.hdu.edu.cn/showproblem.php?pid=3237 用f[i,j,k,s]表示从前i本书中取出j本，没被取出书的状态为k(k不仅要表示书存在的种类，还要具体表示哪类书存在)，没被取出书的最后一本高度为s时，剩下书的最小mess值。由于书按高度分类共有8类，可以用八位二进制来表示剩余书的状态，如果对应位为1则表明该类书存在。各类书存在与否，状态众多，这里可以进行状态压缩。 不考虑被拿出来的书的原因是，我们可以把这些书放到最恰当的位置，对前面求最优值不会产生影响。现在由前i-1本书推后面：对于第i本书，若要取f[i,j+1,k,s]=min{f[i,j+1,k,s],f[i-1,j,k,s]}；若不取分两种情况：第i本书的高度与前面相同时，f[i,j,k,s]=min{f[i,j,k,s],f[i-1,j,k,s]};第i本书的高度与前面不同时，f[i,j,k|(1<<h[i]),h[i]]=min{f[i,j,k|(1<<h[i]),h[i]], f[i,j,k,s]+1}. 最后的答案为：min{f[n,j,k,s]+num(k)},num(k)={k^(书最初的状态)}这个二进制数中1的个数，表示被拿出来的书的种类数。见代码：
#include<iostream>
#define min(a,b) (a<b?a:b)
using namespace std;
const int inf=10000000;
int n,m,begin;
int h[105],num[1<<8];
int f[2][105][1<<8][9];
void Init()
{
int i,j;
memset(num,0,sizeof(num));
for(i=0;i<(1<<8);i++)
{
for(j=0;j<8;j++)
if(i&(1<<j)) num[i]++;
}
}
int main()
{
int test=1;
Init();
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
int i,j,k,s;
begin=0;
for(i=1;i<=n;i++)
{
scanf("%d",&h[i]);
h[i]-=25;
begin=begin|(1<<h[i]);
}
for(i=0;i<=m;i++)
for(j=0;j<(1<<8);j++)
for(k=0;k<=8;k++)
f[0][i][j][k]=inf;
f[0][0][0][8]=0;
for(i=1;i<=n;i++)
{
for(j=0;j<=m;j++)
for(k=0;k<(1<<8);k++)
for(s=0;s<=8;s++)
f[i&1][j][k][s]=inf;
for(j=0;j<=i-1&&j<=m;j++)
for(k=0;k<(1<<8);k++)
for(s=0;s<=8;s++)
if(f[(i-1)&1][j][k][s]!=inf)
{
if(j<m)f[i&1][j+1][k][s]=min(f[i&1][j+1][k][s],f[(i-1)&1][j][k][s]);
if(h[i]==s) f[i&1][j][k][s]=min(f[i&1][j][k][s],f[(i-1)&1][j][k][s]);
else f[i&1][j][k|(1<<h[i])][h[i]]=min(f[i&1][j][k|(1<<h[i])][h[i]],f[(i-1)&1][j][k][s]+1);
}
}
int ans=inf;
for(i=0;i<=m;i++)
for(j=0;j<(1<<8);j++)
for(k=0;k<8;k++)
if(f[n&1][i][j][k]!=inf)
{
int temp=j^begin;
if(ans>f[n&1][i][j][k]+num[temp])
ans=f[n&1][i][j][k]+num[temp];
}
printf("Case %d: %d\n\n",test++,ans);
}
//system("pause");
return 0;
}
posted @
2010-08-23 10:56 wuxu 阅读(408) |
评论 (0) |
编辑 收藏
背包. 题目来源：
http://acm.hdu.edu.cn/showproblem.php?pid=3236初看题目可以知道这是个背包问题，但物品分为普通和特殊两种，并且要求特殊的全部得到。如果只有这两个限制，可以做两次二维背包，先做特殊物品背包，然后把不满足题目要求的状态删掉(同时可以判断能否满足女友的要求)，再做普通物品背包。但是，题目又多了个特殊情况，就是可以免费赠送一个物品，那么可以通过加维来处理。用f[i][j][s]表示得到的最大happy值，其中i表示第一张购物卷，j表示第二张购物卷，s==0表示未赠送，s==1表示已赠送。
普通物品：f[i][j][s]=max{f[i][j][s],f[i-price[k]][j][s]+hap[k],f[i][j-price[k]][s]+hap[k]} (s=0,1)
另外当s==1时还有一种情况，f[i][j][1]=max{f[i][j][1],f[i][j][0]+hap[k]}
特殊物品：f[i][j][0]=max{f[i-price[k]][j][0]+hap[k],f[i][j-price[k]][0]+hap[k]}
f[i][j][1]=max{f[i-price[k]][j][1]+hap[k],f[i][j-price[k]][1]+hap[k],f[i][j][0]+hap[k]}
详细见代码：
#include<iostream>
using namespace std;
int v1,v2,n;
int price[305],hap[305],spec[305];
int f[505][55][2];
int main()
{
int test=1;
while(scanf("%d%d%d",&v1,&v2,&n)!=EOF&&(v1||v2||n))
{
int i,j,k,s,total_spec=0;
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&price[i],&hap[i],&spec[i]);
if(spec[i]) total_spec+=hap[i];
}
memset(f,-1,sizeof(f));
f[0][0][0]=0;
for(k=1;k<=n;k++)
{
if(!spec[k]) continue;
for(i=v1;i>=0;i--)
for(j=v2;j>=0;j--)
{
f[i][j][1]=-1;
if(f[i][j][0]!=-1&&f[i][j][1]<f[i][j][0]+hap[k])
f[i][j][1]=f[i][j][0]+hap[k];
if(i-price[k]>=0&&f[i-price[k]][j][1]!=-1&&f[i][j][1]<f[i-price[k]][j][1]+hap[k])
f[i][j][1]=f[i-price[k]][j][1]+hap[k];
if(j-price[k]>=0&&f[i][j-price[k]][1]!=-1&&f[i][j][1]<f[i][j-price[k]][1]+hap[k])
f[i][j][1]=f[i][j-price[k]][1]+hap[k];
f[i][j][0]=-1;
if(i-price[k]>=0&&f[i-price[k]][j][0]!=-1&&f[i][j][0]<f[i-price[k]][j][0]+hap[k])
f[i][j][0]=f[i-price[k]][j][0]+hap[k];
if(j-price[k]>=0&&f[i][j-price[k]][0]!=-1&&f[i][j][0]<f[i][j-price[k]][0]+hap[k])
f[i][j][0]=f[i][j-price[k]][0]+hap[k];
}
}
bool flag=false;
for(i=0;i<=v1;i++)
for(j=0;j<=v2;j++)
for(s=0;s<2;s++)
{
if(f[i][j][s]==total_spec)
flag=true;
else f[i][j][s]=-1;
}
if(!flag)
{
printf("Case %d: -1\n\n",test++);
continue;
}
for(k=1;k<=n;k++)
{
if(spec[k]) continue;
for(i=v1;i>=0;i--)
for(j=v2;j>=0;j--)
{
if(f[i][j][0]!=-1&&f[i][j][1]<f[i][j][0]+hap[k])
f[i][j][1]=f[i][j][0]+hap[k];
for(s=0;s<2;s++)
{
if(i-price[k]>=0&&f[i-price[k]][j][s]!=-1&&f[i][j][s]<f[i-price[k]][j][s]+hap[k])
f[i][j][s]=f[i-price[k]][j][s]+hap[k];
if(j-price[k]>=0&&f[i][j-price[k]][s]!=-1&&f[i][j][s]<f[i][j-price[k]][s]+hap[k])
f[i][j][s]=f[i][j-price[k]][s]+hap[k];
}
}
}
int ans=-1;
for(i=0;i<=v1;i++)
for(j=0;j<=v2;j++)
for(s=0;s<2;s++)
if(ans<f[i][j][s])
ans=f[i][j][s];
printf("Case %d: %d\n\n",test++,ans);
}
//system("pause");
return 0;
}
posted @
2010-08-22 11:08 wuxu 阅读(302) |
评论 (0) |
编辑 收藏BFS. 题目来源: http://acm.hdu.edu.cn/showproblem.php?pid=1175
由于bfs按层次进行搜所,得到的是从起点到终点的最短路径,但是题目要求我们找一条转向不超过2次的.因此我们可以在此基础上加上一个记录转向次数的数组.对于那些被扩展的点,如果它的转向次数小于等于数组记录的值,那么还可以再次入队列.如下面一组数据:
1 1 1 0 1
1 0 0 0 1
2 0 2 0 1
1 0 1 0 1
1 1 0 0 1
2
5 2 1 5
5 2 1 2
考虑 5 2 1 5这组,如果我们优先扩展上面,则点(2,4)先被标记为1(代表有一次转弯), 然而按此条路径显然不行.但是我们在扩展红色这条路时,可以把(2,4)继续如队列(当前情况扩展时转弯也为1),显然这条路满足条件.
我做这道题时,想到的是按行列扩展,结果队列爆掉了.因为太多重复无用的点进入了队列.
详细见代码:
#include<iostream>
#include<queue>
using namespace std;
const int inf=10000;
int map[1005][1005];
int hash[1005][1005];
int n,m,p;
int x1,y1,x2,y2;
int dir[4][2]={-1,0,1,0,0,-1,0,1};
typedef struct node
{
int x,y,times,direc;
node(){}
node(int xx,int yy,int tt,int ff):x(xx),y(yy),times(tt),direc(ff){}
}NODE;
bool bfs()
{
queue<NODE> q;
NODE temp,tt;
q.push(NODE(x1,y1,0,-1));
hash[x1][y1]=0;
while(!q.empty())
{
temp=q.front();
q.pop();
for(int i=0;i<4;i++)
{
tt.x=temp.x+dir[i][0];
tt.y=temp.y+dir[i][1];
if(temp.direc==-1) {tt.direc=i;tt.times=0;}
else if(i==temp.direc) {tt.direc=temp.direc;tt.times=temp.times;}
else {tt.direc=i;tt.times=temp.times+1;}
if(tt.x>=1&&tt.x<=n&&tt.y>=1&&tt.y<=m&&tt.times<=2&&tt.times<=hash[tt.x][tt.y])
{
if(map[tt.x][tt.y]==0||(tt.x==x2&&tt.y==y2))
{
hash[tt.x][tt.y]=tt.times;
if(tt.x==x2&&tt.y==y2)
return true;
q.push(tt);
}
}
}
}
return false;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&(m||n))
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&map[i][j]);
scanf("%d",&p);
while(p--)
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
hash[i][j]=inf;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(map[x1][y1]!=map[x2][y2]||map[x1][y1]==0||(x1==x2&&y1==y2)) printf("NO\n");
else if(bfs()) printf("YES\n");
else printf("NO\n");
}
}
//system("pause");
return 0;
}
posted @
2010-08-21 11:05 wuxu 阅读(1960) |
评论 (1) |
编辑 收藏
floyd+枚举. 题目来源:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1178 我们将每一个格子看作一个结点,将该结点与附近的骑士能一步到达的结点连一条边.然后用floyd求出每对结点间的最段路径,这就是骑士从一个格子走到另外一个格子的最小步数.对于国王我们可以直接用坐标来求出他通往任意两个格子间的最小步数. 然后枚举他们的汇聚点和国王与骑士的汇合点,再枚举是哪个骑士和国王回合.取最小的那个值.详细见代码:
#include<iostream>
#include<cmath>
using namespace std;
const int inf=100000000;
int location[64],knight[64][64];
int kn_dir[8][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};
char str[130];
void floyd()
{
int i,j,k;
for(k=0;k<64;k++)
for(i=0;i<64;i++)
for(j=0;j<64;j++)
{
if(knight[i][j]>knight[i][k]+knight[k][j])
knight[i][j]=knight[i][k]+knight[k][j];
}
}
void Init()
{
int i,j;
for(i=0;i<64;i++)
for(j=0;j<64;j++)
{
if(i==j) knight[i][j]=0;
else knight[i][j]=inf;
}
for(i=0;i<64;i++)
{
for(j=0;j<8;j++)
{
int x=i/8+kn_dir[j][0];
int y=i%8+kn_dir[j][1];
if(x>=0&&x<8&&y>=0&&y<8)
{
knight[i][x*8+y]=1;
}
}
}
floyd();
}
int main()
{
int i,j,k,num,ans=inf;
Init();
scanf("%s",str);
for(i=0,num=0;str[i];i+=2)
{
location[num++]=8*(str[i+1]-'1')+(str[i]-'A');
}
for(i=0;i<64;i++)
for(j=0;j<64;j++)
{
int xx=abs(location[0]/8-j/8);
int yy=abs(location[0]%8-j%8);
int king_len=xx>yy ? xx:yy;
int knight_len=inf;
for(k=1;k<num;k++)
{
int temp=0;
for(int v=1;v<num;v++)
if(v!=k)
{
temp+=knight[location[v]][i];
}
temp+=knight[location[k]][j]+knight[j][i];
if(knight_len>temp) knight_len=temp;
}
if(knight_len==inf&&king_len<ans) ans=king_len;
else if(king_len+knight_len<ans) ans=king_len+knight_len;
}
printf("%d\n",ans);
//system("pause");
return 0;
}
posted @
2010-08-20 16:34 wuxu 阅读(207) |
评论 (0) |
编辑 收藏
DP(递归形式). 用f[a0,a1,a2,a3,a4]表示每种商品数量分别为a0,a1,a2,a3,a4时的最小价格.则f[a0,a1,a2,a3,a4]=min{f[a0-b0,a1-b1,a2-b2,a3-b3,a4-b4]+priceb,f[a0-c0,a1-c1,a2-c2,a3-c3,a4-c4]+pricec,......}.bi表示第一种优惠组合中各商品的数量,priceb为对应的优惠价. 以此类推. 此题用记忆化DP较好, 详细见代码:
#include<iostream>
#include<map>
using namespace std;
int B,S,N;
int num[6];
int offer[105][6];
int price[105];
int f[6][6][6][6][6];
int dp(int a0,int a1,int a2,int a3,int a4)
{
if(f[a0][a1][a2][a3][a4]!=-1)
return f[a0][a1][a2][a3][a4];
int i,j,temp=100000000;
for(i=0;i<B+S;i++)
{
if(a0>=offer[i][0]&&a1>=offer[i][1]&&a2>=offer[i][2]&&a3>=offer[i][3]&&a4>=offer[i][4])
{
if(temp>dp(a0-offer[i][0],a1-offer[i][1],a2-offer[i][2],a3-offer[i][3],a4-offer[i][4])+price[i])
temp=dp(a0-offer[i][0],a1-offer[i][1],a2-offer[i][2],a3-offer[i][3],a4-offer[i][4])+price[i];
}
}
f[a0][a1][a2][a3][a4]=temp;
return temp;
}
int main()
{
int i,j,c,k,p,s;
map<int,int> ref;
memset(num,0,sizeof(num));
memset(offer,0,sizeof(offer));
scanf("%d",&B);
for(i=0;i<B;i++)
{
scanf("%d%d%d",&c,&k,&p);
ref[c]=i;
num[i]=k;
price[i]=p;
offer[i][i]=1;
}
scanf("%d",&S);
for(i=B;i<B+S;i++)
{
scanf("%d",&N);
for(j=0;j<N;j++)
{
scanf("%d%d",&c,&k);
offer[i][ref[c]]=+k;
}
scanf("%d",&price[i]);
}
memset(f,-1,sizeof(f));
f[0][0][0][0][0]=0;
int ans=dp(num[0],num[1],num[2],num[3],num[4]);
printf("%d\n",ans);
//system("pause");
return 0;
}
posted @
2010-08-20 10:05 wuxu 阅读(175) |
评论 (0) |
编辑 收藏
DP .首先求出任意两个村庄间(包括端点)建一个邮局后,到邮局的最短距离和,记为min_dis[i][j],当邮局建到中点时min_dis[i][j]最小. 用f[i][j]表示前i个邮局建在前j个村庄.则f[i][j]=min{f[i-1][k]+min_dis[k+1][j]，i-1<=k<j}.见代码：
#include<iostream>
using namespace std;
int v,p;
int vill[305];
int f[35][305];
int min_dis[305][305];
int main()
{
int i,j,k;
scanf("%d%d",&v,&p);
for(i=1;i<=v;i++)
scanf("%d",&vill[i]);
memset(min_dis,0,sizeof(min_dis));
for(i=1;i<=v;i++)
for(j=i+1;j<=v;j++)
{
int mid=(i+j)/2;
for(k=i;k<mid;k++)
{
min_dis[i][j]+=vill[mid]-vill[k];
}
for(k=mid+1;k<=j;k++)
{
min_dis[i][j]+=vill[k]-vill[mid];
}
}
for(i=1;i<=v;i++) f[1][i]=min_dis[1][i];
for(i=2;i<=p;i++)
for(j=i;j<=v;j++)
{
int minn=100000000;
for(k=i-1;k<=j-1;k++)
{
if(f[i-1][k]+min_dis[k+1][j]<minn)
minn=f[i-1][k]+min_dis[k+1][j];
}
f[i][j]=minn;
}
printf("%d\n",f[p][v]);
//system("pause");
return 0;
}
posted @
2010-08-19 12:45 wuxu 阅读(161) |
评论 (0) |
编辑 收藏
DP. 用f[i][j]表示前i个月末人数为j时的最小开支.则f[i][j]=min{f[i-1][k]+cost(i,j)},其中k表示第i-1个月的人数,cost(i,j)为第i个月的开支.当k<=j时,cost(i,j)=hire*(j-k)+j*salary;当k>j时,cost(i,j)=fire*(k-j)+j*salary.详细见代码:
#include<iostream>
using namespace std;
const int inf=100000000;
int hire,fire,sal;
int mon,men[13];
int f[13][10000];
int main()
{
while(scanf("%d",&mon)!=EOF&&mon)
{
scanf("%d%d%d",&hire,&sal,&fire);
int i,j,k,MAX_NUM=0;
for(i=1;i<=mon;i++)
{
scanf("%d",&men[i]);
if(MAX_NUM<men[i]) MAX_NUM=men[i];
}
for(i=men[1];i<=MAX_NUM;i++)
f[1][i]=hire*i+sal*i;
for(i=2;i<=mon;i++)
for(j=men[i];j<=MAX_NUM;j++)
{
int minn=inf;
for(k=men[i-1];k<=MAX_NUM;k++)
{
if(k<=j&&minn>f[i-1][k]+hire*(j-k)+j*sal)
minn=f[i-1][k]+hire*(j-k)+j*sal;
else if(k>j&&minn>f[i-1][k]+fire*(k-j)+j*sal)
minn=f[i-1][k]+fire*(k-j)+j*sal;
}
f[i][j]=minn;
}
int ans=inf;
for(i=men[mon];i<=MAX_NUM;i++)
if(f[mon][i]!=0&&f[mon][i]<ans)
ans=f[mon][i];
printf("%d\n",ans);
}
return 0;
}
posted @
2010-08-18 21:35 wuxu 阅读(329) |
评论 (0) |
编辑 收藏