马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
在做 dp 的时间经常在某个细节正法扣，总的说还是没把握住标题的特性性和 dp 的团体架构。既然能一眼看出来是 dp 题，当根据标题特性列出个通例的 dp 式子，之后才有优化的资源。这是一样寻常 dp 题的流程，重点在列出像样的 dp 式子，写一大坨不可用也不可优化的极度、特别式子是没故意义的，要在把握 dp 的线性的底子上实行状态转移，才气将光怪陆离的 dp 题化归成一套有迹可循的体系和模子。
读原题面，叽里呱啦写了千把字，结果末了一行给了下面这段话（
<hr> 简而言之：
给你 m 个 1 到 n 之间的整数，你要找到多少个巨细为固定的 k 的闭区间，使得全部这些数都在你找到的某个区间内。你须要最小化这些区间的并集的巨细，并输出此巨细。本题里区间/区间并集的巨细，被界说为，这个区间/区间并集里整数的个数。
1 ≤ k ≤ n ≤ 1 0 9 , 1 ≤ m ≤ 3 ⋅ 1 0 5 , p i ≤ n 1\le k\le n\le 10^9,1\le m\le 3\cdot 10^5,p_i\le n 1≤k≤n≤109,1≤m≤3⋅105,pi≤n 且互不类似。
<hr> 科场做法
科场上做 dp 题时脑筋很乱，到末了着实不可推出来也推出一个很乱的式子，只过了两个样例，显然地暴毙，挂光光了，分析一开始思绪的走向就不对。以后开头的推理要更加审慎，开头思绪歪背面很难跳出来。
这是科场的代码， f i , 0 / 1 f_{i,0/1} fi,0/1 表现 i i i 当开头（末了）时席卷前 i i i 个点的最小值。自己看了都绷不住。
- #include<bits/stdc++.h>
- using namespace std;
- const int N=3e5+5;
- int n,k,m,p[N],f[N][2],l[N];
- int main(){
-
-
- freopen("cpu.in","r",stdin);
- freopen("cpu.out","w",stdout);
- scanf("%d%d%d",&n,&k,&m);
- for(int i=1;i<=m;i++) scanf("%d",p+i);
- sort(p+1,p+m+
|
发表于 2026-1-14 05:13:55