Programming/Nicola at master · ZimuW/Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//
//  main.cpp
//  Kattis
//
//  Created by Zimu Wang on 10/17/15.
//  Copyright (c) 2015 Zimu Wang. All rights reserved.
//

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <list>
#include <deque>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#include <sstream>
#include <vector>
#include <iomanip>

using namespace std;
int compute(int slot,int step, vector<int> &array)
{
    int sum1=INFINITY;
    int sum2=INFINITY;
    if (slot+step+1==array.size()-1)
        return array[slot+step+1]+array[slot];
    if (slot+step+1<array.size())
        sum1=compute(slot+step+1,step+1,array);
    if (slot-step>0 && slot!=1)
        sum2=compute(slot-step,step,array);

    cout<<slot<<" "<<step<<" "<<min(sum1,sum2)+array[slot]<<endl;
    return min(sum1,sum2)+array[slot];

};

int main()
{
    int number;
    vector<int> array;
    cin>>number;
    array.resize(number+1);
    for (int i=1;i<=number;i++)
        cin>>array[i];
    int DP[number+1][number+1];
    memset(DP,INFINITY,sizeof(DP));
    for (int j=number-1;j>=0;j--)
        for (int i=1;i<=number;i++)
        {
            int sum1=INFINITY;
            int sum2=INFINITY;
            if (i+j+1==array.size()-1)
                DP[i][j] = array[i+j+1]+array[i];
            else
            {if (i+j+1<array.size())
                sum1=DP[i+j+1][j+1];
            if (i-j>0 && i!=1)
                sum2=DP[i-j][j];
                DP[i][j]=min(sum1,sum2)+array[i];
            };
        };
    cout<<DP[1][0]-array[1]<<endl;


}