3 条题解
-
1
更好的阅读体验： https://blog.csdn.net/tenkuo/article/details/163498113
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 5010; struct node { LL x, t; } a[N * 2]; LL dp[2 * N][2], p[2 * N][2]; // 两倍 N 就会炸空间，使用滚动数组 // dp[l][r][0]：守卫在 l，只剩 [l, r] 没有被熄灭 的最小时间 // dp[l][r][1]：守卫在 r，只剩 [l, r] 没有被熄灭 的最小时间 // 为什么是闭区间？因为守卫可以选择不熄灭那个位置上的灯，这样方便计算 // 隐含规则：必须在合法的时间才能走到 l 或者 r（后面代码会讲） bool cmp(node na, node nb) { if (na.x != nb.x) { return na.x < nb.x; // 保证 dp 处理从左到右 } return na.t < nb.t; // 按时间顺序排（一般情况不影响答案） } int main () { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i ++) { LL l, r, t; cin >> l >> r >> t; a[i * 2 - 1] = {l, t}; a[i * 2] = {r, t}; } n *= 2; sort (a + 1, a + n + 1, cmp); memset(dp, 0x7f, sizeof(dp)); LL inf = dp[0][0]; memset(p, 0, sizeof(p)); // p 数组代表的是上一个 len 的 dp 数组 // 第一次转移时范围是 [1, n]，不存在什么 len = n + 1 // 所以不会用到，不初始化也行 dp[1][0] = max(a[1].x, a[1].t); // dp[1][n][0] dp[1][1] = max(a[n].x, a[n].t); // dp[1][n][1] LL ans = inf; for (int len = n; len >= 1; len --) { for (int i = 1; i + len - 1 <= n; i ++) { int j = i + len - 1; // 下面二维数组，想象中间维数插了个 [j] if (i >= 2) { // 守卫从 i - 1 走到 i dp[i][0] = min(dp[i][0], p[i - 1][0] + a[i].x - a[i - 1].x); // 守卫从 i - 1 走到 j dp[i][1] = min(dp[i][1], p[i - 1][0] + a[j].x - a[i - 1].x); } if (j <= n - 1) { // 守卫从 j + 1 走到 i dp[i][0] = min(dp[i][0], p[i][1] + a[j + 1].x - a[i].x); // 守卫从 j + 1 走到 j dp[i][1] = min(dp[i][1], p[i][1] + a[j + 1].x - a[j].x); } dp[i][0] = max(dp[i][0], a[i].t); dp[i][1] = max(dp[i][1], a[j].t); // 这里就是隐含规则，当前状态 i 或 j 是没有熄灭的 // 但你必须在 a[i].t 或 a[j].t 及之后时刻到这里 if (len == 1) { // 当 len = 1 时，代表 i = j，只有 [i, i] 没被熄灭 // 手动操作一下就熄灭了，直接统计答案 ans = min(ans, min(dp[i][0], dp[i][1])); } } for (int i = 1; i <= n; i ++) { p[i][0] = dp[i][0]; p[i][1] = dp[i][1]; dp[i][0] = inf; dp[i][1] = inf; // 更新 p 数组，并初始化 dp数组 } } cout << ans << "\n"; return 0; } -
0
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n; struct N{ ll x,t; }a[10010]; bool cmp(N a,N b){ if(a.x!=b.x)return a.x<b.x; return a.t<b.t; } ll dp[2][10010][2];//dp[i][j][0/1]表示只剩下i~j之间的点没有走，现在在i/j的最小时间 int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1;i<=n;i++){ ll l,r,t; cin>>l>>r>>t; a[i*2-1]={l,t}; a[i*2]={r,t}; //将区间拆成两个点，显然在要先走到其中一个点，之后在走到另一个点的过程中区间会被填满 } n<<=1; memset(dp,0x3f,sizeof(dp)); sort(a+1,a+1+n,cmp); int now=0; dp[now][n][0]=max(a[1].x,a[1].t); dp[now][n][1]=max(a[n].x,a[n].t); for(int i=n-1;i;i--){//先转移i=1的情况 dp[now][i][0]=max(a[1].t,dp[now][i+1][1]+abs(a[1].x-a[i+1].x)); dp[now][i][1]=max(a[i].t,dp[now][i+1][1]+abs(a[i].x-a[i+1].x)); } ll ans=2e18; now^=1; for(int i=2;i<=n;i++,now^=1){//由于是滚动数组，要枚举的是i，从[i-1,j]和[i,j+1]转移过来只需要记录上一个i和倒序枚举j即可 memset(dp[now],0x3f,sizeof(dp[now])); for(int j=n;j>=i;j--){ dp[now][j][0]=min(dp[now][j][0],dp[now^1][j][0]+abs(a[i-1].x-a[i].x));//简单的转移 dp[now][j][1]=min(dp[now][j][1],dp[now^1][j][0]+abs(a[i-1].x-a[j].x)); if(j<n){ dp[now][j][0]=min(dp[now][j][0],dp[now][j+1][1]+abs(a[j+1].x-a[i].x)); dp[now][j][1]=min(dp[now][j][1],dp[now][j+1][1]+abs(a[j+1].x-a[j].x)); } dp[now][j][0]=max(dp[now][j][0],a[i].t); dp[now][j][1]=max(dp[now][j][1],a[j].t); if(i==j){//i=j就是全部被满足 ans=min(ans,min(dp[now][j][0],dp[now][j][1])); } } } cout<<ans; return 0; } -
0
题目大意:
需要我们在特定的时间后熄灭 到 盏灯，初始时在原点上。
思路:
有一个特别难想的做法，可以将区间拆解为两个点在 这个时刻之前这两盏灯不能熄灭，所以可以先对它进行排序。然后设计区间 。 表示除了 和 之间的灯是亮的其他都熄灭了且当前在区间的最左边或最右边。每一种情况都可以由 和 转移过来（详细转移请看代码），但是要和时间取一个最大值，因为没到时间不能熄灭。最后因为空间会爆，所以要记录上一个长度的 数组，来消掉一维。
三维代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5005; const ll inf=LONG_LONG_MAX; ll dp[2*N][2*N][2]; struct node{ ll x,t; }a[2*N]; bool cmp(node x,node y){ if(x.x==y.x){ return x.t<y.t; } return x.x<y.x; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); ll n,ans=inf; cin>>n; for(int i=1;i<=n;i++){ ll l,r,t; cin>>l>>r>>t; a[i*2-1]={l,t}; a[i*2]={r,t}; } n=n*2; sort(a+1,a+1+n,cmp); for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ dp[i][j][0]=inf; dp[i][j][1]=inf; } } dp[1][n][0]=max(a[1].x,a[1].t); dp[1][n][1]=max(a[n].x,a[n].t); for(int len=n;len>=1;len--){ for(int i=1;i+len-1<=n;i++){ int j=i+len-1; if(i-1>=1){ dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+a[i].x-a[i-1].x); dp[i][j][1]=min(dp[i][j][1],dp[i-1][j][0]+a[j].x-a[i-1].x); } if(j+1<=n){ dp[i][j][1]=min(dp[i][j][1],dp[i][j+1][1]+a[j+1].x-a[j].x); dp[i][j][0]=min(dp[i][j][0],dp[i][j+1][1]+a[j+1].x-a[i].x); } dp[i][j][0]=max(dp[i][j][0],a[i].t); dp[i][j][1]=max(dp[i][j][1],a[j].t); if(len==1){ ans=min(ans,min(dp[i][j][1],dp[i][j][0])); } } } cout<<ans<<"\n"; return 0; }正解代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5005; const ll inf=LONG_LONG_MAX; ll dp[2*N][2],p[2*N][2]; struct node{ ll x,t; }a[2*N]; bool cmp(node x,node y){ if(x.x==y.x){ return x.t<y.t; } return x.x<y.x; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); ll n,ans=inf; cin>>n; for(int i=1;i<=n;i++){ ll l,r,t; cin>>l>>r>>t; a[i*2-1]={l,t}; a[i*2]={r,t}; } n=n*2; sort(a+1,a+1+n,cmp); for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ dp[i][0]=inf; dp[i][1]=inf; } } dp[1][0]=max(a[1].x,a[1].t); dp[1][1]=max(a[n].x,a[n].t); for(int len=n;len>=1;len--){ for(int i=1;i+len-1<=n;i++){ int j=i+len-1; if(i-1>=1){ dp[i][0]=min(dp[i][0],p[i-1][0]+a[i].x-a[i-1].x); dp[i][1]=min(dp[i][1],p[i-1][0]+a[j].x-a[i-1].x); } if(j+1<=n){ dp[i][1]=min(dp[i][1],p[i][1]+a[j+1].x-a[j].x); dp[i][0]=min(dp[i][0],p[i][1]+a[j+1].x-a[i].x); } dp[i][0]=max(dp[i][0],a[i].t); dp[i][1]=max(dp[i][1],a[j].t); if(len==1){ ans=min(ans,min(dp[i][1],dp[i][0])); } } for(int i=1;i<=n;i++){ p[i][0]=dp[i][0]; p[i][1]=dp[i][1]; dp[i][0]=inf; dp[i][1]=inf; } } cout<<ans<<"\n"; return 0; }
- 1
信息
- ID
- 12544
- 时间
- 4000ms
- 内存
- 1100MiB
- 难度
- 9
- 标签
- 递交数
- 18
- 已通过
- 4
- 上传者
-
huangzheng