最近一直在想写点东西，又担心自己偷懒，写着写着没后续，让人看的累，所以迟迟不敢下笔。刚刚在网上闲逛，翻了翻动态空间记录的学生训练的情形，偶尔瞟了一眼日期，7月21日，不管三七二十一，先动笔吧。

2018年5月一个周五中午刚刚下课，突然接到侯哥电话，说让我替他去西安出差带学生打icpc西安邀请赛（比赛地点西北工业大学），挂了电话后就跟负责行程学生张佳联系，了解他们的行程安排，然后就翻开携程比对火车飞机的时间，最后确定了周六早晨坐飞机飞往西安，这样就跟同学们差不多的时间赶到西安。

周六早晨起床发现落枕了，由于赶时间简单的用刮痧板处理了一下就往机场赶，周六早晨的机场显得空空荡荡，离飞机起飞还有接近一个小时，就在机场书店买了一本<自控力>的书籍阅读，时不时跟张佳联系，了解他们的情况，突然张佳发来一条消息说：“比赛在西工大长安校区”。心里一愣，赶紧拿起手机在地图上搜索长安校区，一看结果直接懵逼，长安校区坐落在西安市区东面3-40公里，第一感觉好远。在西安西面的咸阳国际机场下了飞机，就坐机场大巴去市内，在好几年未见面的叔叔家吃了顿午饭，意外的见到了从新加坡回来休假的堂弟，自从我工作以后好像就没见过他，吃完饭，跟叔叔一家人聊了一会，叔叔亲自开车把我送到长安校区，印证了确实远。

由于对整个安排不是很熟悉，所以我就在西工大长安校区正门口等六名队员，他们十一二点下的火车，我想应该很快就到了吧。结果在西安初春的寒风中跟西工大的保安聊了一个半小时，他们才姗姗来迟，原来，为了节约费用，他们坐了那趟超多站的公交（好像有60站），在路上摇了两个多小时才到，等我们赶到报到处，邀请赛热身赛已经开始了，办好手续他们去打热身赛去了，我就在下面跟组织方聊天，跟刘君瑞老师初次见面。

等他们打完热身赛已经五点半了，原后就去吃晚餐，在吃晚餐的时候跟其他教练随便聊聊，突然听到一个教练说起武汉两年前的大雨淹城，一问是湖工大徐承志老师，一见是老乡就互留联系方式，方便以后联系，后来很多时候我有不清楚的地方，就去咨询徐老师，徐老师给我帮助良多。

奔波一天，晚饭后匆匆回酒店安顿，洗完澡头发也没吹倒头就睡，没想到西安的春天后半夜还是有些冷，第二天早晨起来感觉颈椎更严重了，给后来带来了很多麻烦。吃完早餐就去西工大候场，由于邀请赛未在体育馆进行，错失了首次见识体育馆千人现场赛的震撼场面。

比赛正式开始后，教练们就在会议室看榜等待，期间跟徐老师聊天，了解了icpc一些基本信息。快中午的时候，西安同学过来碰面，毕业一别过了20几年未曾谋面，边吃边聊各自人生际遇，聊聊其他大学同学的情况。

吃完饭回来一看榜单已经封榜，原来排名靠前的队伍一路下滑，快跌出银牌区，另一支队伍仍没进奖牌区，感觉获奖希望不大。等到比赛结束，立即跟他们会面，听说排名靠后的队伍在封榜期间A了一题，感觉又看到了希望。由于他们要去赶火车，所以就匆匆坐车去火车站。我由于前面答应刘君瑞老师出席颁奖典礼，所以就暂时留下了。

由于种种原因，颁奖典礼推迟了半个小时，我一看机票时间有点紧张，就参加了铜牌的颁奖，原后拿着队员获得的一银一铜奖牌坐上同学的车匆匆赶往机场。

这一次西安之行紧张而有收获，这时我还没想过要参与到icpc中来。

Problem H. ICPC Quest

来源：ACM International Collegiate Programming Contest, Syrian Collegiate Programming Contest (2014) Syria, September, 23, 2014 CF链接Gym 100500H

Problem Description

Noura Boubou is a Syrian volunteer at ACM ACPC (Arab Collegiate Programming Contest) since 2011. She graduated from Tishreen University where she studied Information Technology. She is the head of the photography team responsible for photo-shooting the Arabs joining the world finals.

On the first day of the world finals last year, Dr Mohamed Fo’ad, the ACPC Regional Contest Director, asked Noura to play one of the ICPC Quests. ICPC Quests are a set of challenges that might require the contestants to move around the city searching for some monuments, solving puzzles, or getting a high score in a certain game. The rules of the quests states that the contestants will post the answer to the quest to Twitter using these hashtags #ICPC2014 #QuestN where N is the quest number. The contestant will post a photo or a short video (a Vine) of the challenge he accomplished. The scores of the challenges are accumulated and the one with the highest score will get an Android tablet.

Noura was so enthusiastic about the Quest number 14. Quest 14 was about a grid of n rows and m columns, and each cell of the grid contains an integer, and whenever a contestant steps on a cell he is going to add its value to his total accumulated sum. The task was to start from the top left cell located at (1,1) and to move only right or down in order to get to cell (n,m), and during this journey the contestant has to get the maximum sum possible. The player who can get the maximum possible score is announced as the winner of this quest.

You will be given the description of the grid, please help Noura determining the maximum possible score she can get.

Input

The first line will be the number of test cases T. Each test case starts with 2 integers n, m where n is the number of rows while m is the number of columns. They will be followed by n rows each containing m numbers, and the absolute value of the number in each cell will not exceed 100.

1 <= T <= 100

1 <= n,m <= 1000

-100 <= celli,j <= 100

Output

For each test case print a single line containing:

Case_x:_y

x is the case number starting from 1.

y is is the required answer.

Replace underscores with spaces.

Examples

quest.in

2

3 3

1 2 3

-1 -2 -3

1 1 1

2 3

1 1 2

2 1 5

Standard Output

Case 1: 4

Case 2: 9

Hint：题目要求是求出从左上角（1,1）到右下角（n，m），只能向右或向下，找到最大的路径和；

第一种代码：（从最后一排最后一列开始向前找）

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

int a[1100][1100], b[1100][1100];
int main()
{
    int t, i, j, k = 1, n, m;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &n, &m);
        for(i = 1; i <= n; i++)
        {
            for(j = 1; j <= m; j++)
            {
                scanf("%d", &a[i][j]);
            }
        }
        for(i = n; i >= 1; i--)
        {
            for(j = m; j >= 1; j--)
            {
                if(i == n && j == m)
                    b[i][j] = a[i][j];
                else if(i == n)
                    b[i][j] = a[i][j] + b[i][j + 1];
                else if(j == m)
                    b[i][j] = a[i][j] + b[i + 1][j];
                else
                {
                    if(b[i][j + 1] >= b[i + 1][j])
                        b[i][j] = a[i][j] + b[i][j + 1];
                    else if(b[i][j + 1] < b[i + 1][j])
                        b[i][j] = a[i][j] + b[i + 1][j];
                }
            }
        }
        printf("Case %d: %d\n", k++, b[1][1]);
    }
    return 0;
}


第二种代码：（从前往后找，边输入边查询）

//#include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

int a[1100][1100], b[1100][1100];
int main()
{
    int t, i, j, k = 1, n, m;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &n, &m);
        for(i = 1; i <= n; i++)
        {
            for(j = 1; j <= m; j++)
            {
                scanf("%d", &a[i][j]);
                b[i][j] = INT_MIN; // 定义无穷小
                if(i == 1 && j == 1)
                    b[i][j] = a[i][j];
                if(i > 1)
                    b[i][j] = max(b[i - 1][j] + a[i][j], b[i][j]);
                if(j > 1)
                    b[i][j] = max(b[i][j - 1] + a[i][j], b[i][j]);
            }
        }
        printf("Case %d: %d\n", k++, b[n][m]);
    }
    return 0;
}


 

java ACM
转载至恋上猫的鱼
Java做ACM-ICPC的特点：
(1) 在一般比赛中，Java程序会有额外的时间和空间，而实际上经过实验，在执行计算密集任务的时候Java并不比C/C++慢多少，只是IO操作较慢而已。
(2) Java 简单而功能强大，有些东西用Java实现起来更为方便，比如高精度。
(3) 用Java不易犯细微的错误，比如C/C++中的指针， “if (n = m) ... ” 等
(4) 目前来看Eclipse已成基本配置，写Java程序反而比C/C++更方便调试。在具体竞赛时也算多一种选择。
(5) 学会Java对以后工作有好处。现在国外很多地方会Java的人比会C/C++的人多。
下面说一下ACM-ICPC队员初用Java编程所遇到的一些问题：
1. 基本输入输出：
(1)
JDK 1.5.0 新增的
Scanner类为输入提供了良好的基础，简直就是为ACM-ICPC而设的。
一般用法为：
import java.io.*
import java.util.*
public class Main
{
public static void main(String args[])
{
Scanner cin = new Scanner(new BufferedInputStream(System.in));
...
}
}
当然也可以直接 Scanner cin = new Scanner(System.in);
只是加Buffer可能会快一些
(2)
读一个整数：   int n = cin.nextInt();         相当于   scanf("%d", &n);   或 cin >> n;
读一个字符串：String s = cin.next();         相当于   scanf("%s", s);     或 cin >> s;
读一个浮点数：double t = cin.nextDouble();   相当于   scanf("%lf", &t); 或 cin >> t;
读一整行：     String s = cin.nextLine();     相当于   gets(s);           或 cin.getline(...);
判断是否有下一个输入可以用 cin.hasNext() 或 cin.hasNextInt() 或 cin.hasNextDouble() 等，具体见 TOJ 1001 例程。
(3)
输出一般可以直接用 System.out.print() 和 System.out.println()，前者不输出换行，而后者输出。
比如：System.out.println(n);   // n 为 int 型
同一行输出多个整数可以用
System.out.println(new Integer(n).toString() + " " + new Integer(m).toString());
也可重新定义：
static PrintWriter cout = new PrintWriter(new BufferedOutputStream(System.out));
cout.println(n);
(4)
对于输出浮点数保留几位小数的问题，可以使用DecimalFormat类，
import java.text.*;
DecimalFormat f = new DecimalFormat("#.00#");
DecimalFormat g = new DecimalFormat("0.000");
double a = 123.45678, b = 0.12;
System.out.println(f.format(a));
System.out.println(f.format(b));
System.out.println(g.format(b));
这里0指一位数字，#指除0以外的数字。
2. 大数字
BigInteger 和 BigDecimal 是在java.math包中已有的类，前者表示整数，后者表示浮点数
用法：
不能直接用符号如+、-来使用大数字，例如：
(import java.math.*)   // 需要引入 java.math 包
BigInteger a = BigInteger.valueOf(100);
BigInteger b = BigInteger.valueOf(50);
BigInteger c = a.add(b)   // c = a + b;
主要有以下方法可以使用：
BigInteger add(BigInteger other)
BigInteger subtract(BigInteger other)
BigInteger multiply(BigInteger other)
BigInteger divide(BigInteger other)
BigInteger mod(BigInteger other)
int compareTo(BigInteger other)
static BigInteger valueOf(long x)
输出大数字时直接使用 System.out.println(a) 即可。
3. 字符串
String 类用来存储字符串，可以用charAt方法来取出其中某一字节，计数从0开始：
String a = "Hello";     // a.charAt(1) = ’e’
用substring方法可得到子串，如上例
System.out.println(a.substring(0, 4))     // output "Hell"
注意第2个参数位置上的字符不包括进来。这样做使得 s.substring(a, b) 总是有 b-a个字符。
字符串连接可以直接用 + 号，如
String a = "Hello";
String b = "world";
System.out.println(a + ", " + b + "!");     // output "Hello, world!"
如想直接将字符串中的某字节改变，可以使用另外的StringBuffer类。
4. 调用递归(或其他动态方法)
在主类中 main 方法必须是 public static void 的，在 main 中调用非static类时会有警告信息，
可以先建立对象，然后通过对象调用方法：
public class Main
{
...
void dfs(int a)
{
if (...) return;
...
dfs(a+1);
}
public static void main(String args[])
{
...
Main e = new Main();
e.dfs(0);
...
}
}
5. 其他注意的事项
(1) Java 是面向对象的语言，思考方法需要变换一下，里面的函数统称为方法，不要搞错。
(2) Java 里的数组有些变动，多维数组的内部其实都是指针，所以Java不支持fill多维数组。
数组定义后必须初始化，如 int[] a = new int[100];  (3) 布尔类型为 boolean，只有true和false二值，在 if (...) / while (...) 等语句的条件中必须为boolean类型。        在C/C++中的 if (n % 2) ... 在Java中无法编译通过。    (4) 下面在java.util包里Arrays类的几个方法可替代C/C++里的memset、qsort/sort 和 bsearch:    Arrays.fill()   Arrays.sort()   Arrays.binarySearch()