题目链接
吐槽一波：这题目没有数据范围有点NT
和前面的修缮长城差不多了，就是裸的区间DP（实际上更简单一些），然后本题需要注意的只有两个地方，一个是在宝物恰好消失的那一秒是到达是取不到宝物的；另外一个地方是区间DP的一种写法是会T的——也就是在讲最优矩阵链乘接触的写法，而写逆推的话是OK的，真是一道奇怪的题目
#include <set> #include <map> #include <stack> #include <queue> #include <math.h> #include <cstdio> #include <string> #include <bitset> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define lowbit(x) (x&(-x)) #define mkp(x,y) make_pair(x,y) #define mem(a,x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> P; const double eps=1e-8; const double pi=acos(-1.0); const int inf=0x3f3f3f3f; const ll INF=1e18; const int Mod=1e9+7; const int maxn=1e4+10; int a[maxn],t[maxn]; int d[maxn][maxn][2]; int n; int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); while(~scanf("%d",&n)){ for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&t[i]); memset(d,0x3f,sizeof d); for(int i=1;i<=n;i++) d[i][i][0]=d[i][i][1]=0; for(int i=n-1;i>=1;i--) for(int j=i+1;j<=n;j++){ if(j>1){ if(d[i][j-1][1]+a[j]-a[j-1]<t[j]) d[i][j][1]=min(d[i][j][1],d[i][j-1][1]+a[j]-a[j-1]); if(d[i][j-1][0]+a[j]-a[i]<t[j]) d[i][j][1]=min(d[i][j][1],d[i][j-1][0]+a[j]-a[i]); } if(i<n){ if(d[i+1][j][1]+a[j]-a[i]<t[i]) d[i][j][0]=min(d[i][j][0],d[i+1][j][1]+a[j]-a[i]); if(d[i+1][j][0]+a[i+1]-a[i]<t[i]) d[i][j][0]=min(d[i][j][0],d[i+1][j][0]+a[i+1]-a[i]); } } int ans=min(d[1][n][0],d[1][n][1]); if(ans<inf) printf("%d\n",ans); else puts("No solution"); } return 0; }