动态规划+深度优先搜索 TLE两个点

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2904 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2904 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2908 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2904 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 2908 KiB, score = 10
测试数据 #5: TimeLimitExceeded, time = 1203 ms, mem = 2904 KiB, score = 0
测试数据 #6: Accepted, time = 0 ms, mem = 2904 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 2904 KiB, score = 10
测试数据 #8: TimeLimitExceeded, time = 1203 ms, mem = 2904 KiB, score = 0
测试数据 #9: Accepted, time = 0 ms, mem = 2908 KiB, score = 10
TimeLimitExceeded, time = 2406 ms, mem = 2908 KiB, score = 80
代码
#include <algorithm>
#include <iostream>
using namespace std;
int m,s,t,MaxDist;
struct DP {
  int f,g;
}dp[300001];
inline void dfs(int nowtime,int nowm,int nowdist) {
  MaxDist = max(MaxDist,nowdist);
  if (!nowtime) return;
  if (nowm >= 10) dfs(nowtime-1,nowm-10,nowdist+60);
  else dfs(nowtime-1,nowm+4,nowdist);
}
int main() {
  ios :: sync_with_stdio(false);
  cin >> m >> s >> t;
  dp[0].f = dp[0].g = 0;
  for (int i = 1;i <= t;i++) {
    MaxDist = -9999999;
    dfs(i,m,0);
    dp[i].g = MaxDist;
    dp[i].f = max(dp[i-1].f+17,dp[i].g);
  }
  if (dp[t].f < s) {
    cout << "No\n" << dp[t].f;
    return 0;
  }
  while (dp[t].f >= s) t--;
  cout << "Yes\n" << ++t;
  return 0;
}

0 条评论

目前还没有评论...

信息

ID
1431
难度
5
分类
动态规划 | 背包 点击显示
标签
递交数
6158
已通过
1917
通过率
31%
被复制
22
上传者