Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 400 points
Takahashi is trying to catch many Snuke.
There are five pits at coordinates 00, 11, 22, 33, and 44 on a number line, connected to Snuke's nest.
Now, NN Snuke will appear from the pits. It is known that the ii-th Snuke will appear from the pit at coordinate X_iXi at time T_iTi, and its size is A_iAi.
Takahashi is at coordinate 00 at time 00 and can move on the line at a speed of at most 11.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.
Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.
Input is given from Standard Input in the following format:
NN T_1T1 X_1X1 A_1A1 T_2T2 X_2X2 A_2A2 \vdots⋮ T_NTN X_NXN A_NAN
Print the answer as an integer.
Copy
3 1 0 100 3 3 10 5 4 1
Copy
101
The optimal strategy is as follows.
It is impossible to catch both the first and second Snuke, so this is the best he can.
Copy
3 1 4 1 2 4 1 3 4 1
Copy
0
Takahashi cannot catch any Snuke.
Copy
10 1 4 602436426 2 1 623690081 3 3 262703497 4 4 628894325 5 3 450968417 6 1 161735902 7 1 707723857 8 2 802329211 9 0 317063340 10 2 125660016
Copy
2978279323
设f[i][j]表示最大值的一个集合, i表示第i秒, j表示第 j 个坑。
则有状态转移方程f[i][j] = a[i][j] + f[i - 1][j], 在原地不动;
f[i][j] = max(f[i][j], a[i][j] + f[i - 1][j - 1]), 从f[i - 1][j - 1] 得来
f[i][j] = max(f[i][j], a[i][j] + f[i - 1][j + 1]),向后退, 从f[i - 1][j + 1] 得来。
Code:
- #pragma GCC optimize(1)
- #pragma GCC optimize(2)
- #pragma GCC optimize(3, "Ofast", "inline")
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
-
- using namespace std;
-
- const int N = 100010;
-
- typedef long long LL;
-
- LL n, m, res;
- LL a[N][6], f[N][6];
- unordered_map<int, int> mp;
-
- signed main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- cin >> n;
- for(int i = 1; i <= n; i ++ )
- {
- LL t, x, d;
- cin >> t >> x >> d;
- a[t][x] = d;
- }
- memset(f, -0x3f, sizeof f);
- f[0][0] = 0;
- for(int i = 1; i <= 100000; i ++ )
- {
- for(int j = 0; j <= 4; j ++ )
- {
- f[i][j] = a[i][j] + f[i - 1][j];
- if(j > 0) f[i][j] = max(f[i][j], a[i][j] + f[i - 1][j - 1]);
- if(j < 4) f[i][j] = max(f[i][j], a[i][j] + f[i - 1][j + 1]);
- }
- }
- for(int i = 0; i <= 4; i ++ )
- res = max(res, f[100000][i]);
- cout << res << endl;
- }