작업하던거 안된다해서 4시부터 풀기 시작했음

센서 꼽아놓고 init 시키니까 안되는거던데 암튼


cash를

시작점 기준 왼쪽 현재 남아있는거 1000 오른쪽 현재 남아있는거 1000

그리고 방금전에 왼쪽으로 달려왔는지 오른쪽으로 달려왔는지 stat 2 해서


1000 * 1000 * 2 DP로 잡고 품


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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
 
typedef struct {
    int position;
    int cost;
} Ramp;
 
int cmp(const Ramp &a, const Ramp &b)
{
    return a.position < b.position;
}
 
 
vector< Ramp > ramp;
int cash[1003][1003][2];    
int n;
 
int makeans(int left, int right , bool stat)
{
    if (left == -1)
    {
        left = n + 2;
    }
    int& ret = cash[left][right][stat];
 
    if (ret != -1)
    {
        return ret;
    }
 
    ret = 1000000001;
    int now;
 
    if (stat == 0)
    {
        now = right - 1;
    }
    else
    {
        if (left == n + 2)
        {
            now = 0;
        }
        else
        {
            now = left + 1;
        }
    }
 
    if ((left == n+2)&&(right==n+1))
    {
        ret = 0;
    }
    else if(left == n+2)
    {
        ret = (ramp[right].position - ramp[now].position)*ramp[right].cost + makeans(left,right+1,0);
    }
    else if (right == n + 1)
    {
        ret = (ramp[now].position - ramp[left].position)*ramp[left].cost + makeans(left-1,right,1);
    }
    else
    {
        ret = min((ramp[right].position - ramp[now].position)*(ramp[right].cost+ramp[left].cost) + makeans(left, right + 1, 0),
                    (ramp[now].position - ramp[left].position)*(ramp[right].cost + ramp[left].cost) + makeans(left - 1, right, 1));
    }
 
    return ret;
}
 
int main()
{
    int now;
 
    scanf(" %d %d", &n, &now);
 
    while (n--)
    {
        Ramp dummy;
        scanf(" %d %d", &dummy.position, &dummy.cost);
        ramp.push_back(dummy);
    }
    /**/
    sort(ramp.begin(), ramp.end(),cmp);
 
    n = 0;
    now = now - 1;
    for (int i = 1; i < ramp.size(); i++)
    {
        if (ramp[n].position == ramp[i].position)
        {
            ramp[n].cost += ramp[i].cost;
        }
        else
        {
            n++;
            ramp[n].position = ramp[i].position;
            ramp[n].cost = ramp[i].cost;
        }
 
        if (i == now)
        {
            now = n;
        }
    }
 
    int sumcost=0;
    
    for (int i = 0; i < now; i++)
    {
        sumcost += ramp[i].cost;
        ramp[i].cost = sumcost;
    }
 
    sumcost = 0;
 
    for (int i = n; i > now; i--)
    {
        sumcost += ramp[i].cost;
        ramp[i].cost = sumcost;
    }
 
    for (int i = 0; i < 1003; i++)
    {
        for (int j = 0; j < 1003; j++)
        {
            cash[i][j][0] = -1;
            cash[i][j][1] = -1;
        }
    }
    
    printf("%d ",makeans(now - 1 , now + 1, 0));
 
    return 0;
}
cs

담문제 

우수마을
https://www.acmicpc.net/problem/1949

심심한사람 같이풀사람 같이 풀쟈
전 밥먹고 와서 시작함