2162: Inuyasha And the Monsters
| Result | TIME Limit | MEMORY Limit | Run Times | AC Times | JUDGE |
|---|---|---|---|---|---|
 |
5s | 8192K | 573 | 184 | Standard |
Now, they want to kill a great many of monsters. Those monsters hide in several palaces. The palaces are built in a straight line from the south to the north. they must go from the south to the north and can only move straight ahead. That is to say, they can't go from north to the south at any time.
But there is another problem. All the monsters in front of the current palace will escape immedietely if the number of monsters they killed in the current palace is more than the ones of those palaces.
Surely Inuyasha wants to kill as many monsters as he can. Can you help him?
Note: Once they determine to kill the monsters in a palace, they must kill them all.
Input
The input file contains one or more test cases, followed by a line containing the number 0 that signals the end of the file. Each test case consists of two lines.the first line contains a single integer M(M<10000), which indicates the number of the palaces; the second line contains M integers, which are the number of the monsters in the palaces, from south to north. You may assume that all numbers are less than 2^31.
Output
The output for every case begins with a line containing "Case #k:", where k is the number of the test case starting from 1. Then print a single integer which is the number of the monsters they has killed. It is also in a single line. Print a blank line between every two cases.
Sample Input
5 1 2 3 4 5 5 4 5 3 1 2 0
Sample Output
Case #1: 15 Case #2: 9
Problem Source: chihao
#include<stdio.h>
int dp[10000];
int a[10000];
int main()
{
int n,i,j;
int l=1;
int m=0;
while(scanf("%d",&n)==1&&n)
{
if(m==0) m++;
else printf("/n");
printf("Case #%d:/n",l++);
for(i=0;i<n;i++){scanf("%d",&a[i]);}
dp[0]=a[0];
for(i=1;i<n;i++)
{
dp[i]=a[i];
for(j=0;j<i;j++)
{
if(a[i]>=a[j]&&dp[i]<dp[j]+a[i]) dp[i]=dp[j]+a[i];
}
}
int max=0;
for(i=0;i<n;i++)
{
if(dp[i]>max) max=dp[i];
}
printf("%d/n",max);
}
return 0;
}