地址:http://codeforces.com/problemset/problem/455/E

给你1个递归公式让你算出f(i,j)的值

• f(1, j) = a[j], 1 ≤ j ≤ n.
• f(i, j) = min(f(i - 1, j), f(i - 1, j - 1)) + a[j], 2 ≤ i ≤ n, i ≤ j ≤ n.

做了一下没做出来,才发现原来只有17个人过了...还是先放放吧!

下面是我的代码先贴着,样例能过,但是某些数据就死循环了,可能是递归的时候,有出口没考虑到吧...

#include <stdio.h>
#include <algorithm>
using namespace std;

int a[10005], t[10005];

int f(int i, int j, int n)
{
    if(i == 1 && 1 <= j && j <= n) return a[j];
    if(i >= 2 && i <= n && i <= j && j <= n)
        return min(f(i - 1, j - 1, n), f(i - 1, j, n)) + a[j];
}

int main(int argc, char *argv[])
{
    int n, m, v1, v2;
    while(scanf("%d", &n) != EOF)
    {
        for(int i = 1; i <= n; scanf("%d", &a[i++])) ;
        scanf("%d", &m);
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d", &v1, &v2);
            t[i] = f(v1, v2, n);
        }
        for(int i = 1; i <= m; printf("%d\n", t[i++])) ;
    }
    return 0;
}