Problem#
The aliens from outer space have (finally) invaded Earth. Defend yourself, or disintegrate, be assimilated by them, or become food. So far, we cannot determine.
The aliens follow known attack patterns. There are $N$ aliens attacking, the $i$-th attacking alien will appear at time $a_i$, at a distance $d_i$ from you, and it must be eliminated before time $b_i$, otherwise, you will be the one eliminated.
Your weapon is an area shockwave device that can be set to any given power. If set to power $R$, it will instantly destroy all aliens within a distance of $R$ (inclusive), while it will also consume $R$ units of fuel cells.
Find the minimum cost to destroy all aliens (how much fuel cells are consumed), while ensuring your own safety.
Solution#
Interval DP problem + 1
Let f[i][j] be the minimum cost to eliminate aliens whose start and end times are both in [i, j].
Transition, find the farthest alien in this range, enumerate the time it is eliminated.
Then it will be divided into two parts, f[i][time-1] and f[time+1][j].
Bug#
The discretized b array and the input b array got mixed up (
Code#
#include<bits/stdc++.h>
using namespace std;
const int N = 310;
int T, n;
int a[N], b[N], d[N];
const int M = 610;
int lib[M], btop, lic[M], ctop;
int f[M][M];
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
cin >> T;
while (T -- )
{
cin >> n;
btop = ctop = 0;
for(int i = 1;i <= n;i++)
{
cin >> a[i] >> b[i] >> d[i];
lib[++ btop] = a[i], lib[++ btop] = b[i];
}
sort(lib + 1, lib + 1 + btop);
for(int i = 1;i <= btop;i++)
{
if(lib[i] != lib[i - 1])
{
lic[++ ctop] = lib[i];
}
}
for(int i = 1;i <= n;i++)
{
a[i] = lower_bound(lic + 1, lic + 1 + ctop, a[i]) - lic;
b[i] = lower_bound(lic + 1, lic + 1 + ctop, b[i]) - lic;
// cout << a[i] << " " << b[i] << endl;
}//a, b are now both in the range of 0 to ctop
memset(f, 0x3f, sizeof f);
for(int len = 1;len <= ctop;len++)
{
for(int i = 1;i + len - 1 <= ctop;i++)
{
int j = i + len - 1;
int maxid = 0;
for(int k = 1;k <= n;k++)
{
if(i <= a[k] && b[k] <= j)
{
if(d[maxid] < d[k])
{
maxid = k;
}
}
}
if(maxid == 0)
{
f[i][j] = 0;
continue;
}
for(int k = a[maxid];k <= b[maxid]/**/;k++)
{
f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j] + d[maxid]);
}
}
}
printf("%d\n", f[1][ctop]);
}
return 0;
}