2015
04-14

Dark Parth

In the dark path, the single figure is walking difficultly in the listless rainfall. No one knows his real destination.

‘Young, have you ever tasted the loneliness walking in dark path; have you ever run about madly just to avoid the pain in the deep heart?’
After BiYao’s death, XiaoFan changed to GuiLi .Running in such darkness, leaving the rain wet out his clothes, leaving the darkness cover up his eyes, he will never regret!

Now, we separate the path into n parts with the same length (1<=N<=1000).Every part has its value Ai (-1000<=Ai<=1000). If Xiaofan walks through the ith part of the path, he will get the hurt Ai. His trump ShaoHuoGun will give him S chances to fly (1<=S<=100). Every chance can help him get through one part of the path without any hurt. But there’s a limit: The length of his fly Si should be longer than La and shorter than Lb (1<=La<=Si<=Lb<=n).
Your job is to find the best way for XiaoFan to have the least hurt.
Hit: Two different fly paths can’t cover each other, and times of fly can be fewer than the given times S.

There are several test cases. The first line is an integer N, then the second line have three integers Lb, La, S, then followed N integers A1.A2…An.The test end by n = 0.

There are several test cases. The first line is an integer N, then the second line have three integers Lb, La, S, then followed N integers A1.A2…An.The test end by n = 0.

10
3 2 3
3 1 -5 -9 2 -1 1 -7 9 10

10
4 3 4
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

0

-21
-10

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>

using namespace std;

const int maxn=1001;
const int maxs=101;

int dp[maxs][maxn];
int data[maxn];

int min(int a,int b){
return a<b?a:b;
}

int main(){
int n,s,la,lb;
while(scanf("%d",&n)&&n){
scanf("%d%d%d",&lb,&la,&s);
memset(dp,0,sizeof(dp));
int i,j,k;
for(i=1;i<=n;i++){
scanf("%d",&data[i]);//
dp[0][i]=data[i];
dp[0][i]+=dp[0][i-1];//当使用0次飞行特权时走过i段的悲伤值为1到i段悲伤值的和
}
for(i=1;i<=s;i++){
for(j=1;j<=n;j++){
dp[i][j]=dp[i][j-1]+data[j];//首先让dp[i][j]=dp[i][j-1],当然这里也可以放在下面的选小值的函数中
for(k=la;k<=lb && k<=j;k++){
dp[i][j]=min(dp[i][j],dp[i-1][j-k]);//状态转移 很好理解
}
}
}
int ans=1<<30;
for(i=0;i<=s;i++){
ans=min(dp[s][n],ans);//n段都走完选悲伤值最小的
}
printf("%d\n",ans);
}
return 0;
}


1. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。