河南省第六届大学生程序设计竞赛
Problem A: T1异 形 卵 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 26 Solved: 14 [Submit][Status][Web Board] Description
我们探索宇宙，是想了解浩瀚星空的奥妙，但我们却很少意识到宇宙深处藏匿的危险，它们无时无刻不紧盯着我们的地球。如果外星人拜访我们，结果可能与哥伦布当年踏足美洲大陆不会有什么两样，这是历史，也是现实。
在ZDM-777星球上发现的休眠异形卵，其外表与常见的卵不同，表面被一层石墨覆盖。当人走近时，那层石墨开始消融，能看到里面的异形卵正在活动，异形卵是活物，具备一些热量或压力传感器这些基本的中枢神经系统，通过感知周围的热量，选择热量最大处寄生。不过，假如周围有不适合被寄生处，异形卵就选择休眠。
周围的热量可以用一串整数a1,a2,……,an来表示，异形卵具有一定的长度L，异形卵总是选择ai+ai+1+…+ai+L-1达到最大值处寄生。若周围的热量低于0，异形卵则选择休眠。
异形卵是如何感知它的寄生处呢？
【约束条件】
2≤K≤5 L≤N, 1≤L≤10 1≤N≤1000 -100≤ ai≤100
数据之间有一个空格。
Input 第一行： K 表示有多少组测试数据。
接下来对每组测试数据有2行
第1行: L N
第2行：a1 a2 …… aN
Output 对于每组测试数据，输出一行：异形卵能寄生的起始位置。若有多处可以寄生，则选择小的起始位置。若无处可以寄生，则输出0。
Sample Input 2 3 5 30 0 100 -30 100 3 5 -100 80 -80 -100 80 Sample Output 3 0
就是给定长度，让你找，这个长度下，最长连续序列和最大的地方，基本的使用线段和技巧就行。
#include
using namespace std;
const int maxn=1001;
int T,l,n;
int a[maxn];
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&T))
{
while(T--)
{
scanf("%d %d",&l,&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]+=a[i-1];
}
int maxe=0;
int p=0;
for(int i=0;i<=n-l;i++)
{
int sum=a[i+l]-a[i];
//cout<<sum<<endl;
if(sum>maxe)
{
maxe=sum;
p=i+1;
}
}
printf("%d
",maxe>0?p:0);
}
}
return 0;
}
Problem B: T2外星人的供给站 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 22 Solved: 8 [Submit][Status][Web Board] Description 外星人指的是地球以外的智慧生命。外星人长的是不是与地球上的人一样并不重要，但起码应该符合我们目前对生命基本形式的认识。比如，我们所知的任何生命都离不开液态水，并且都是基于化学元素碳（C）的有机分子组合成的复杂有机体。
42岁的天文学家Dr. Kong已经执著地观测ZDM-777星球十多年了，这个被称为“战神”的红色星球让他如此着迷。在过去的十多年中，他经常有一些令人激动的发现。ZDM-777星球表面有着明显的明暗变化，对这些明暗区域，Dr. Kong已经细致地研究了很多年，并且绘制出了较为详尽的地图。他坚信那些暗区是陆地，而亮区则是湖泊和海洋。他一直坚信有水的地方，一定有生命的痕迹。Dr. Kong有一种强烈的预感，觉得今天将会成为他一生中最值得纪念的日子。 这天晚上的观测条件实在是空前的好，ZDM-777星球也十分明亮，在射电望远镜中呈现出一个清晰的暗红色圆斑。还是那些熟悉的明暗区域和极冠，不过，等等，Dr. Kong似乎又扑捉到曾看到过的东西，那是什么，若隐若现的。他尽可能地睁大了眼睛，仔细地辨认。哦，没错，在一条直线上，又出现了若干个极光点连接着星球亮区，几分钟后，极光点消失。
Dr. Kong大胆猜想，ZDM-777星球上的湖泊和海洋里一定有生物。那些极光点就是ZDM-777星球上的供给站，定期给这些生物提出维持生命的供给。
不妨设，那条直线为X轴，极光点就处在X轴上，N个亮区P1，P2，…Pn就分布在若干个极光点周围。
接着，Dr. Kong 又有惊人的发现，所有的亮区Pi都处在某个半径为R的极光点圆内。去掉一个极光点就会有某些亮区Pj不处在覆盖区域内。
Dr. Kong想知道，至少需要多少个极光点才能覆盖所有的湖泊和海洋。
【约束条件】
2≤K≤5 1≤R≤50 1≤N≤100 -100≤PXi PYi≤100 | PYi | ≤ R
R, PXi PYi都是整数。数据之间有一个空格。
Input 第一行： K 表示有多少组测试数据。
接下来对每组测试数据：
第1行: N R
第2~N+1行： PXi PYi (i=1,……,N)
Output 对于每组测试数据，输出一行： 最少需要的极光点数。
Sample Input 2 3 2 1 2 -3 1 2 1 1 5 5 5 Sample Output 2 1
分析：
一开始想的太简单了，感觉每次我设置一个极光点的时候就尽量往右设置，这样保证每次设置一个，就贪心的让他尽可能的照亮最多个点，想多照亮几个点没问题，但尽量往右走就不对了，比如：
所以：
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=110;
int T,n,r;
class P
{
public:
int s,e;
};
bool operator < (const P &a,const P &b)
{
return a.s<b.s;
}
P a[maxn];
int ans;
int check(int cnt,int x)
{
while(a[cnt].s<=x&&x<=a[cnt].e)
{
cnt++;
}
cnt--;
return cnt;
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&T))
{
while(T--)
{
scanf("%d %d",&n,&r);
r=r*r;
for(int i=1;i<=n;i++)
{
scanf("%d %d",&a[i].s,&a[i].e);
int dx=sqrt(r-a[i].e*a[i].e);
a[i].e=a[i].s+dx;
a[i].s-=dx;
}
sort(a+1,a+n+1);
ans=0;
int cnt=1;
int nextcnt=1;
int maxp=1;
while(cnt<=n)
{
nextcnt=cnt;
for(int i=a[cnt].s;i<=a[cnt].e;i++)
{
int p=check(cnt,i);
if(p>nextcnt)
{
nextcnt=p;
}
}
ans++;
cnt=nextcnt+1;
}
printf("%d
",ans);
}
}
return 0;
}
Problem C: T3最舒适的路线 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 13 Solved: 7 [Submit][Status][Web Board] Description
异形卵潜伏在某区域的一个神经网络中。其网络共有N个神经元（编号为1,2,3,…,N），这些神经元由M条通道连接着。两个神经元之间可能有多条通道。异形卵可以在这些通道上来回游动，但在神经网络中任一条通道的游动速度必须是一定的。当然异形卵不希望从一条通道游动到另一条通道速度变化太大，否则它会很不舒服。
现在异形卵聚居在神经元S点，想游动到神经元T点。它希望选择一条游动过程中通道最大速度与最小速度比尽可能小的路线，也就是所谓最舒适的路线。
【约束条件】
2≤K≤5 1<N≤500 0<M≤5000 1≤ Xi, Yi , S , T ≤N 0< Vi <30000，
Vi是整数。数据之间有一个空格。
Input 第一行： K 表示有多少组测试数据。
接下来对每组测试数据：
第1行: N M
第2~M+1行： Xi Yi Vi (i=1,……,M) 表示神经元Xi 到神经元Yi之间通道的速度必须是Vi
最后一行：S T ( S和T不相等 )
Output
对于每组测试数据，输出一行：如果神经元S到神经元T没有路线，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。
Sample Input 2 3 2 1 2 2 2 3 4 1 3 3 3 1 2 10 1 2 5 2 3 8 1 3 Sample Output 2 5/4
杀鬼题，就是暴力搜索？？？ 枚举我们的最大速度，然后从这个速度往下的路一条条加进来，看看是不是加了一条路之后就能到达终点了，如果可以了，那么我们以当前最大速度能找到的最不颠簸的答案就是当前的解了。 枚举完所有最大速度后就得到了最优解。。。。。。。。。。。
我不写了,人家的代码：
#include //包含c++中所以得头文件
using namespace std;
int father[5050];
int K,N,M;
class node
{
public:
int x,y,v;
}s[5050];
int find(int x)
{
while(x!=father[x])
x=father[x];
return x;
}
void merage(int x,int y)
{
x=find(x);
y=find(y);
if(x>y)
father[x]=y;
else father[y]=x;
}
int cmp(node a,node b)
{
return a.v>b.v;
}
int gcd(int a,int b)
{
while(b!=0)
{
int t=a%b;
a=b;
b=t;
}
return a;
}
int main()
{
int i,j,k,a,b;
int S,T;
double l;
while(cin>>K)
while(K--)
{
cin>>N>>M;
//输入边，但这里只记录了单向边
for(i=0;i<M;i++)
{
cin>>s[i].x>>s[i].y>>s[i].v;
}
//输入开始节点，结束节点
cin>>S>>T;
//将边按照从大到小排序
sort(s,s+M,cmp);
//设l为最大速度
l=INT_MAX*1.0;
//遍历M条边
for(i=0;i<M;i++)
{
//初始化并查集
for(j=0;j<N;j++)
{
father[j]=j;
}
//遍历所有比当前边更慢的边
for(k=i;k<M;k++)
{
//如果这条边能够合并两个点，那么就合并
if(find(s[k].x)!=find(s[k].y))
merage(s[k].x,s[k].y);
//如果找到了一条路就结束
if(find(S)==find(T))break;
}
//如果最大速度为i这条，但找不到路了，那么就跳出
if(k==M)break;
//如果找到了一条路
if(s[i].v*1.0/s[k].v<l)
{
a=s[i].v,b=s[k].v;
l=s[i].v*1.0/s[k].v;
}
}
//如果颠簸度还未INT_MAX，那么说明找不到路
if(l==INT_MAX)
printf("IMPOSSIBLE
");
else if(a%b==0)cout<<a/b<<endl;
else cout<<a/gcd(a,b)<<"/"<<b/gcd(a,b)<<endl;
}
return 0;
}
Problem D: T4探 寻 宝 藏 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 4 Solved: 4 [Submit][Status][Web Board] Description 传说HMH大沙漠中有一个M*N迷宫，里面藏有许多宝物。某天，Dr.Kong找到了迷宫的地图，他发现迷宫内处处有宝物，最珍贵的宝物就藏在右下角，迷宫的进出口在左上角。当然，迷宫中的通路不是平坦的，到处都是陷阱。Dr.Kong决定让他的机器人卡多去探险。
但机器人卡多从左上角走到右下角时，只会向下走或者向右走。从右下角往回走到左上角时，只会向上走或者向左走，而且卡多不走回头路。（即：一个点最多经过一次）。当然卡多顺手也拿走沿路的每个宝物。
Dr.Kong希望他的机器人卡多尽量多地带出宝物。请你编写程序，帮助Dr.Kong计算一下，卡多最多能带出多少宝物。
【约束条件】
2≤k≤5 1≤M, N≤50 0≤Aij≤100 (i=1,….,M; j=1,…,N)
所有数据都是整数。 数据之间有一个空格。
Input
第一行： K 表示有多少组测试数据。
接下来对每组测试数据：
第1行: M N
第2~M+1行： Ai1 Ai2 ……AiN (i=1,……,m)
Output 对于每组测试数据，输出一行：机器人卡多携带出最多价值的宝物数
Sample Input 2 2 3 0 10 10 10 10 80 3 3 0 3 9 2 8 5 5 7 100 Sample Output 120 134
呜呜呜，还是不会做，鬼畜啊，思路是有的，就是枚举出来每一种情况，因为这个问题不能贪心，所以只能枚举，但是如果真的去进行枚举，不加优化，那指定超时。
此时想到了什么？？ DP来消除dfs中那些重复的子问题搜索，就是说假如我第一次选了一条路，那么此时另一条路的所有情况我都算出来，这样避免我们一直重复搜索这条路径。
假设我们同时搜索两条从左上角到右下角的路。那么设一条路是A，一条路是B。 那么A走到(ai,aj),B吧所有剩下能去的地方(bi,bj)都去算一下，并把答案存起来，存到dp[ai][aj][bi][bj]。
然后A再走一步，B继续枚举出来所有可能，存一下，这样最后dp[n][m-1][n-1][m]+a[n][m]就是答案了
其中这一句很重要： if(ix&&jy||i+j!=x+y)continue; //当(i,j) (x,y)点相同或者走的步数不同时，跳过
这句话消除了很多无效情况，被命中的次数超级多，但我找不到优化方法，
#include
#include
#include
#include
#include
using namespace std;
int k,n,m,a[52][52],dp[52][52][52][52];
void dpnm(){
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
for(int x=1;x<=i;x++){
for(int y=1;y<=n;y++){
if(i==x&&j==y||i+j!=x+y)continue; //当(i,j) (x,y)点相同或者走的步数不同时，跳过
int t1=dp[i-1][j][x-1][y],t2=dp[i-1][j][x][y-1],t3=dp[i][j-1][x-1][y],t4=dp[i][j-1][x][y-1]; //四个子位置的值
dp[i][j][x][y]=max(dp[i][j][x][y],max(max(max(t1,t2),t3),t4)+a[i][j]+a[x][y]); //找到其中最大值并加上 (i,j) (x,y)两个位置本身含有的值
}
}
}
}
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&k))
{
while(k--)
{
cin>>m>>n;
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
for(int i=1;i<=m;i++)
{ //最好总1开始输入，
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
dpnm();
printf("%d
",dp[m][n-1][m-1][n]+a[m][n]);
}
}
return 0;
}
Problem E: T5能 源 公 司 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 3 Solved: 1 [Submit][Status][Web Board] Description ZDM能源公司现有一个火力发电厂和M座煤矿。火力发电厂每年需要用煤T吨。该火力发电厂每年正常运作的固定费用为R元（包括人员工资，折旧费，不包括煤的运费）。第I号煤矿每年产量为ai吨，每吨原煤从第I号煤矿运到该火力发电厂的运费为Ci0。
ZDM能源公司现在准备再建立一个火力发电厂，M座煤矿每年开采的原煤将全部供给这两座发电厂。现有N个备选的地址建厂。若在第J号备选地址建厂，新建发电厂每年正常运作的固定费用每年运行的固定费用为hj元。每吨原煤从第I号矿运到J号备选厂址的运费为Cij。
现在的问题是，把新厂地址选取什么位置，M座煤矿开采的原煤应如何分配给两个发电厂，才能使ZDM能源公司每年的总费用（发电厂运行费用与原煤运费之和）达到最小。
【约束条件】
1≤M≤100000 1≤T≤10000 1≤R≤50 1≤N≤50
0≤ai≤500, a1+a2+…+am>=T 0≤ hj ≤100 0≤Ci0，Cij ≤50
所有数据都是整数。 数据之间有一个空格。 i=1,2,…., m j=1,2,…, n
Input
第1行： M T R N
第2行： a1 a2 … am
第3行： h1 h2 … hn
第4行： C10 C20 … Cm0
第5行： C11 C21 … Cm1
… …
第n+4行： C1n C2n … Cmn
Output
第1行：新厂址编号，如果有多个编号满足要求，输出最小的。
第2行：总费用
Sample Input 4 2 7 9 3 1 10 3 6 3 7 1 10 2 7 4 9 1 2 4 3 6 6 8 2 4 10 8 4 10 2 9 2 7 6 6 2 9 3 7 1 2 1 6 9 3 1 10 9 4 2 1 8 2 1 3 4 Sample Output 8 49
这题就是题意表述不清。。。 那T吨是指一定要分配给旧发电厂T吨，剩下的都分配给新发电厂，那么贪心一下就好，看看，有那些煤运到旧厂便宜，而运到新厂贵，我们把这些厂按照差值大小排一下序，先给旧厂安排T吨，剩下的给新厂就好。。
#include
using namespace std;
const int inf=0x3f3f3f3f;
int m,t,r,n;
int c[51][100001];
int a[100001];
int h[51];
class Mei
{
public:
int no;
int price;
int dp;
int numofmei;
};
bool operator < (const Mei &a,const Mei &b)
{
return a.dp>b.dp;
}
Mei mei[100001];
int calc(int num)
{
int ans=r+h[num];
for(int i=1;i<=m;i++)
{
mei[i].price=c[num][i];
mei[i].no=i;
mei[i].dp=mei[i].price-c[0][i];
mei[i].numofmei=a[i];
}
sort(mei+1,mei+1+m);
//处理T吨
int tt=t;
int cnt=1;
while(tt>0)
{
if(mei[cnt].numofmei<=tt)
{
ans+=(mei[cnt].numofmei*c[0][mei[cnt].no]);
tt-=mei[cnt].numofmei;
cnt++;
}
else
{
ans+=(tt*c[0][mei[cnt].no]);
mei[cnt].numofmei-=tt;
tt=0;
}
}
//处理剩下的煤
while(cnt<=m)
{
ans+=(mei[cnt].numofmei*mei[cnt].price);
cnt++;
}
return ans;
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d %d %d %d",&m,&t,&r,&n))
{
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);
}
for(int i=0;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&c[i][j]);
}
}
int ans=inf;
int p=0;
for(int i=1;i<=n;i++)
{
int tans=calc(i);
if(ans>tans)
{
ans=tans;
p=i;
}
}
printf("%d
%d
",p,ans);
}
return 0;
}
Problem F: T6 Card Trick Time Limit: 1 Sec Memory Limit: 128 MB Submit: 5 Solved: 4 [Submit][Status][Web Board] Description The magician shuffles a small pack of cards, holds it face down and performs the following procedure:
-
The top card is moved to the bottom of the pack. The new top card is dealt face up onto the table. It is the Ace of Spades.
-
Two cards are moved one at a time from the top to the bottom. The next card is dealt face up onto the table. It is the Two of Spades.
-
Three cards are moved one at a time…
-
This goes on until the nth and last card turns out to be the n of Spades.
This impressive trick works if the magician knows how to arrange the cards beforehand (and knows how to give a false shuffle). Your program has to determine the initial order of the cards for a given number of cards, 1 ≤ n ≤ 13.
Input On the first line of the input is a single positive integer k, telling the number of test cases to follow. 1 ≤ k ≤ 10 Each case consists of one line containing the integer n. 1 ≤ n ≤ 13
Output For each test case, output a line with the correct permutation of the values 1 to n, space separated. The first number showing the top card of the pack, etc…
Sample Input 2 4 5 Sample Output 2 1 4 3 3 1 4 5 2
题目意思就是我把上边 i 张牌依次移动到下边后，上边第一张牌是i。 数据范围也不大，那么我们倒着模拟一遍。 先把第 n 张牌放到队列里，然后操作 n-1 次， 让后把第 n-1 张牌放到队列，操作 n-2 次。 。。。
然后输出。
#include
using namespace std;
queue s;
int n;
int T;
int main()
{
while(~scanf("%d",&T))
{
while(T--)
{
while(~scanf("%d",&n))
{
for(int i=n;i>=1;i--)
{
s.push(i);
for(int j=0;j!=i;j++)
{
int t=s.front();
s.pop();
s.push(t);
}
}
stack ans;
while(s.size())
{
ans.push(s.front());
s.pop();
}
while(ans.size())
{
printf("%d",ans.top());
ans.pop();
if(ans.size())printf(" ");
else printf("
");
}
}
}
}
return 0;
}
Problem G: T7Adjacent Bit Counts Time Limit: 1 Sec Memory Limit: 128 MB Submit: 3 Solved: 2 [Submit][Status][Web Board] Description
For a string of n bits x1, x2, x3, …, xn, the adjacent bit count of the string is given by fun(x) = x1x2 + x2x3 + x3x 4 + … + xn-1x n which counts the number of times a 1 bit is adjacent to another 1 bit. For example:
Fun(011101101) = 3
Fun(111101101) = 4
Fun (010101010) = 0
Write a program which takes as input integers n and p and returns the number of bit strings x of n bits (out of 2ⁿ) that satisfy Fun(x) = p.
For example, for 5 bit strings, there are 6 ways of getting fun(x) = 2:
11100, 01110, 00111, 10111, 11101, 11011
Input On the first line of the input is a single positive integer k, telling the number of test cases to follow. 1 ≤ k ≤ 10 Each case is a single line that contains a decimal integer giving the number (n) of bits in the bit strings, followed by a single space, followed by a decimal integer § giving the desired adjacent bit count. 1 ≤ n , p ≤ 100
Output For each test case, output a line with the number of n-bit strings with adjacent bit count equal to p.
Sample Input 2 5 2 20 8 Sample Output 6 63426
嗯，是个DP问题，但是我找不到如何进行状态转移。。。
还是，给大佬的打注释吧，呜呜呜。。
注释也打不通顺，，，大佬也不写注释，，，
#include
#include
#include
#include
using namespace std;
int dp[101][101][2];
int n,p;
int main()
{
freopen("in.txt","r",stdin);
int i,j,k;
int t;
//先初始化一下式子长度为1的情况
dp[1][0][0]=1;
dp[1][0][1]=1;
dp[1][1][0]=0;
dp[1][1][0]=0;
//初始化式子长度从2到101的情况，但此时我们只允许出现一个1，所以
for (i=2;i<101;i++)
{
//假如第i位为0，那么答案等于前i-1位以0开头有0个1的个数加上以1开头有0个1的个数
dp[i][0][0]=dp[i-1][0][0]+dp[i-1][0][1];
//假如第i位为1，那么答案等于前i-1位以0开头的个数
dp[i][0][1]=dp[i-1][0][0];
}
//遍历式子长度
for (i=2;i<101;i++)
{
//遍历式子中1的个数
for (j=0;j<i;j++)
{
//当第i位为0时，前i-1位有j个11的情况
dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1];
//当第i位为1时，答案等于前i-1位以0开头，能形成j个11的个数，
//加上前i-1位，以1开头，能形成j-1个11的个数，
//因为我们第i位为1，和这个i-1位以1开头的正好又形成一个11，合起来就是j个11
dp[i][j][1]=dp[i-1][j][0]+dp[i-1][j-1][1];
}
}
scanf("%d",&t);
while (t--)
{
int num;
scanf("%d %d",&n,&p);
printf("%d
",dp[n][p][0]+dp[n][p][1]);
}
return 0 ;
}
Problem H: T8 River Crossing Time Limit: 1 Sec Memory Limit: 128 MB Submit: 1 Solved: 1 [Submit][Status][Web Board] Description
Afandi is herding N sheep across the expanses of grassland when he finds himself blocked by a river. A single raft is available for transportation.
Afandi knows that he must ride on the raft for all crossings, but adding sheep to the raft makes it traverse the river more slowly.
When Afandi is on the raft alone, it can cross the river in M minutes When the i sheep are added, it takes Mi minutes longer to cross the river than with i-1 sheep (i.e., total M+M1 minutes with one sheep, M+M1+M2 with two, etc.).
Determine the minimum time it takes for Afandi to get all of the sheep across the river (including time returning to get more sheep).
Input
On the first line of the input is a single positive integer k, telling the number of test cases to follow. 1 ≤ k ≤ 5 Each case contains:
-
Line 1: one space-separated integers: N and M (1 ≤ N ≤ 1000 , 1≤ M ≤ 500).
-
Lines 2…N+1: Line i+1 contains a single integer: Mi (1 ≤ Mi ≤ 1000)
Output
For each test case, output a line with the minimum time it takes for Afandi to get all of the sheep across the river.
Sample Input 2 2 10 3 5 5 10 3 4 6 100 1 Sample Output 18 50
就是运羊，但加不同只羊会慢多少的情况不同，那么怎么办呢？ 得去一个个试试吧，那么就得DP了。
我们看看，假如我考虑前n头羊，最后一次带m头羊，那么我们最少花费多少时间呢？
dp[n][m] = min{dp[n-m][k]} k=(1,n-m)
这就是状态转移方程了。。
#include
using namespace std;
const int maxn=1001;
int T,n,m;
int a[maxn];
int dp[maxn];
int sum[maxn];
int main()
{
while(~scanf("%d",&T))
{
while(T--)
{
memset(sum,0,sizeof(sum));
scanf("%d %d",&n,&m);
sum[0]=m;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=a[i];
sum[i]+=sum[i-1];
}
dp[0]=-m;
for(int i=1;i<=n;i++)
{
dp[i]=dp[i-1]+m+sum[1];
for(int j=0;j<=i-2;j++)
{
dp[i]=min(dp[i],dp[j]+m+sum[i-j]);
}
}
printf("%d
",dp[n]);
}
}
return 0;
}