坑！

题目链接：

---

 

哎呀呀，好好的一道DP题，太伤心了。。。

思路很快有了，可以定义dp[i]为以第i个任务为结尾的方案中，花费时间最短的。从小到大枚举j，要求满足p[j]+t[j]<=p[i]&&p[j]+t[j]>p[last]（last是指上一个与第i个任务时间不同的任务），然后dp[i]=min(dp[i],dp[j]+t[i])，一开始把dp初始化为inf。在最后应加上第k+1个任务，开始时间为n+1，持续时间为0（注意理清时间点和时间段）。这些都还不算什么，最坑的是我交上去只有30分，死活不知道哪错了，下载了个数据一看，原来最初几个任务的开始时间可以不是1（要先将最开始几个任务初始化，在最前面添加一个点的方式或许也可以躲开坑）！！！

这就涉及到思维问题了，是关注具体的值，还是抽象的关系。。。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 using namespace std; 6  7 const int maxk = 1e4 + 5, inf = 0x3f3f3f3f; 8  9 int p[maxk], t[maxk], dp[maxk];10 11 int main() {12     int n, k;13     scanf("%d%d", &n, &k);14     memset(dp, inf, sizeof(dp));15     p[k + 1] = n + 1;16     for (int i = 1; i <= k + 1; ++i) {17         if (i <= k) scanf("%d%d", &p[i], &t[i]);18         if (p[i] == p[1]) {19             dp[i] = t[i];20             continue;21         }22         int last = i - 1;23         while (p[last] == p[i]) --last;24         for (int j = 0; j < i; ++j)25             if (p[j] + t[j] <= p[i] && p[j] + t[j] > p[last])26                 dp[i] = min(dp[i], dp[j] + t[i]);27     }28     printf("%d", n - dp[k + 1]);29     return 0;30 }