这里记录了一些自己写过的dp题，自己在这方面一直有所欠缺，做题的思路总是不好，那么就开一个专题来记录一下写过的题，希望能有所长进呢。
这个题目需要注意到两点:
1.题目中的序列是环状的
2.我们需要找到两段不重合的子段
那么这两点如何解决呢，第一点的话比较难想，最先开始以为是把序列拼在后面去，结果会出现重复，那么这里的方法是：把每一个序列的值变为负数，然后靠dp方程求出这个序列此时的最大两段子段和 。此时求出的是什么呢，是原来子段中找到的最小两个不重合子段，那么这两个子段把整个序列分为三个部分，因为环状的原因，可以把它拼为两个子段，这样减去两个最小不重合子段就是最大的啦。
对于第二点，如何用dp求解最大不重合子段呢，我们只需要写两个数组f1[ ],f2[ ]，定义f1[i]为在区间[1,i]之间能找到的最大子段，f2[i]为在[i+1,n]之间能找到的最大子段，即可求出呐。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#define INF 0x3f3f3f3f
using namespace std;
int (){
int res=0,f=1;char ch=' ';
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int N=550005;
int n;
int f1[N],f2[N],ans1,ans2,sum,tot,a[N];
int DP(){
int ans=-INF;
for(register int i=1;i<=n;i++)f1[i]=max(f1[i-1],0)+a[i];
for(register int i=1;i<=n;i++)f1[i]=max(f1[i],f1[i-1]);
for(register int i=n;i>=1;i--)f2[i]=max(f2[i+1],0)+a[i];
for(register int i=n;i>=1;i--)f2[i]=max(f2[i+1],f2[i]);
for(register int i=1;i<n;i++)ans=max(ans,f1[i]+f2[i+1]);
return ans;
}
int main(){
n=read();
memset(f1,-INF,sizeof(f1));
memset(f2,-INF,sizeof(f2));
for(register int i=1;i<=n;i++){
a[i]=read();
if(a[i]>0) sum++;
tot+=a[i];
}
ans1=DP();
if(sum==1) printf("%d",ans1);
else{
for(register int i=1;i<=n;i++){
a[i]*=-1;
}
ans2=DP()+tot;
if(ans2==0) ans2=-INF;
printf("%d",max(ans1,ans2));
}
return 0;
}
|
这真的是一道很神奇的题目呢， 思路很清奇，咋一看感觉完全不会写，看了题解才知道需要构建一个矩阵，横边为前一个的两倍，竖边为前一个的三倍，那么我们只需要在每一个图里面找到可行的，就如x选了，那么2x，3x不可选，而4x，6x可选，因此求出每一个图的情况数，因为图是独立的，那么情况数应该乘起来。
解释都写在代码里面啦：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
using namespace std;
int (){
int res=0,f=1;char ch=' ';
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int N=550005;
const int mod=1000000001;
int pos[30],n,mt[30][3005],vis[N],limit[30];
long long dp[30][3005];
long long check(int x){
mt[1][1]=x;memset(limit,0,sizeof(limit));
for(register int i=2;i<=18;i++){
if(mt[i-1][1]*2<=n) mt[i][1]=mt[i-1][1]*2;
else mt[i][1]=n+1;
}
for(register int i=1;i<=18;i++){
for(register int j=2;j<=11;j++){
if(mt[i][j-1]*3<=n) mt[i][j]=mt[i][j-1]*3;
else mt[i][j]=n+1;
}
}
for(register int i=1;i<=18;i++){
for(register int j=1;j<=11;j++){
if(mt[i][j]<=n) limit[i]+=pos[j-1],vis[mt[i][j]]=1;
}
}
for(register int i=0;i<=18;i++){
for(register int j=0;j<=limit[i];j++){
dp[i][j]=0;
}
}
dp[0][0]=1;
for(register int i=0;i<=17;i++){
for(register int j=0;j<=limit[i];j++){
if(dp[i][j]){
for(register int k=0;k<=limit[i+1];k++){
if(!(k&j)&&!(k&(k>>1))){
dp[i+1][k]=(dp[i][j]+dp[i+1][k])%mod;
}
}
}
}
}
return dp[18][0];
}
int main(){
n=read();
pos[0]=1;
for(register int i=1;i<=18;i++) pos[i]=pos[i-1]*2;
long long ans=1;
for(register int i=1;i<=n;i++){
if(!vis[i]) ans=ans*check(i)%mod;
}
printf("%lldn",ans);
return 0;
}
|
这个思路也较为灵活，一个人说有a个人比他菜 pzh比所有人菜 ,b个人比他强，那么在[a+1,n-b]之间的每个人实力是相同的，那么题目意思就化为了找到不相交的子段集合，使总和最大。
这题细节有点多：
1.因为会出现相同的区间，这样的话是满足条件的，但是他们重合了dp时不能算在一起怎么办呢，那么就以l边sort一遍，把相同的集合并在一块，增加其个数就行
2.dp方程如何转移，我们只需要找到离当前[l,r]区间最近的区间即可，也就是二分法找出一个区间，其r‘比当前区间的l小，且最近，所以：dp[i]=max(dp[i-1],dp[k]+b[i].w); b[i].w为当前集合的个数，dp[k]为k∈[1,i−1]时满足Rk < Li的最大的值.
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
using namespace std;
int (){
int res=0,f=1;char ch=' ';
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int N=150005;
struct node{
int w,l,r;
}a[N],b[N];
int n,ans,num1,num2,dp[N];
bool cmp1(node x,node y){
if(x.l==y.l) return x.r<y.r;
return x.l<y.l;
}
bool cmp2(node x,node y){
if(x.r==y.r) return x.l<y.l;
return x.r<y.r;
}
int _find(int x){
int l=1,r=x-1;
while(l<=r){
int mid=(l+r)/2;
if(b[mid].r<b[x].l) l=mid+1;
else r=mid-1;
}
return r;
}
int main(){
n=read();
for(register int i=1;i<=n;i++){
int x=read(),y=read();
if(x+y>=n) continue;
a[++num1].l=x+1;a[num1].r=n-y;
}
sort(a+1,a+1+num1,cmp1);
for(register int i=1;i<=num1;i++){
if(i==1||a[i].l!=a[i-1].l||a[i].r!=a[i-1].r) b[++num2]=a[i],b[num2].w=1;
else if(b[num2].w<b[num2].r-b[num2].l+1) b[num2].w++;
}
sort(b+1,b+1+num2,cmp2);
dp[1]=b[1].w;
for(register int i=2;i<=num2;i++){
int k=_find(i);
dp[i]=max(dp[i-1],dp[k]+b[i].w);
}
printf("%d",n-dp[num2]);
return 0;
}
|
这题运用了贪心+dp的思路来解决。
题目中给出了两个量，一个是打饭时间，一个是吃饭时间，那么很显然，打饭是必须要一个一个来的，而吃饭则没有这样的限制，那么首先排一遍序，将吃饭时间较长的放在前面，那么最后一个吃的肯定是吃饭时间最少的，下面dp一下即可。
因为排队时间是固定的，那么只需要用前缀和记录下前i个人总的排队时间。
定义一个f[ i ] [ j ]代表走到第i个点，甲窗口排队时间为j时吃完饭的最短时间，那么转移方程为下面两个：
如果为max前一个条件时，此时第i个人吃完了还有人在吃，故为前i-1个人吃完饭所需的最小时间。
如果为后一个条件时，第i个人吃完了就全部人吃完了，所以最后的时间点应该是第i个人打完饭的时间加上吃饭的时间。
因为f[i] [j]中的j代表的是在甲窗口排队时间，那么a[ i ] - j就是此时乙窗口排队的时间。其他方面类似。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <bits/stdc++.h>
using namespace std;
int (){
int res=0,f=1;char ch=' ';
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int N=1005;
int n;
struct node{
int x,y;
}t[N];
int f[N][N*15];
int a[N];
bool cmp(node A,node B){
return A.y>B.y;
}
int main(){
n=read();
for(register int i=1;i<=n;i++) t[i].x=read(),t[i].y=read();
sort(t+1,t+1+n,cmp);
memset(f,63,sizeof(f));
for(register int i=1;i<=n;i++){
a[i]=a[i-1]+t[i].x;
}
f[0][0]=0;
for(register int i=1;i<=n;i++){
for(register int j=0;j<=a[i];j++){
if(j>=t[i].x) f[i][j]=min(f[i][j],max(f[i-1][j-t[i].x],j+t[i].y));
f[i][j]=min(f[i][j],max(f[i-1][j],a[i]-j+t[i].y));
}
}
int ans=1<<30;
for(register int i=0;i<=a[n];i++){
ans=min(ans,f[n][i]);
}
printf("%dn",ans);
return 0;
}
|
这种多线程的路径规划问题还挺少见的，记个博客增强一下记忆。
这题的第一A我是拿费用流水过去的（费用流还挺好想，拆了点之后把点内赋为流量1，费用1，路径赋为流量1，费用0，因为要走两次，那么就把第1和第n点拆点内多一条费用0，流量1的边。）
咳咳，这是正经的DP博客，还是讲讲这题DP的思路。
记得之前有一道传纸条的题，它需要两个人从起点走到终点，那么那道题用了一个二维数组f[i] [j]代表两个人分别走到的点，这道题也一样，那么考虑如何转移。
1
2
3
4
5
6
7
8
|
for(register int i=1;i<n;i++){
for(register int j=i+1;j<=n;j++){
for(register int k=1;k<j;k++){
if(l[j][k]&&f[i][k]) f[i][j]=max(f[i][j],f[i][k]+1);
}
f[j][i]=f[i][j];
}
}
|
第一个转移较为的好想，我们令此刻所在点为 j 点,那么它必由前面与其联通的一个点走过来。我们可以看出，如果只是有这一个转移并不行，因为我们只移动了 j 点，而i点的值并未更新。仔细一看你可以发现，i 必比j小，那么我们调换这两个人，即为 f[i] [j]和 f[j] [i]是必相等的，那么我们只需要用f[i] [j]更新f[j] [i]即可。
下面为代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int (){
int res=0,f=1;char ch=' ';
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int N=1005;
int n,m;
map<string,int>z;
int f[N][N],l[N][N];
int main() {
n=read();m=read();
for(register int i=1;i<=n;i++){
string s;cin>>s;
z[s]=i;
}
for(register int i=1;i<=m;i++){
string a,b;cin>>a>>b;
l[z[a]][z[b]]=l[z[b]][z[a]]=1;
}
f[1][1]=1;
for(register int i=1;i<n;i++){
for(register int j=i+1;j<=n;j++){
for(register int k=1;k<j;k++){
if(l[j][k]&&f[i][k]) f[i][j]=max(f[i][j],f[i][k]+1);
}
f[j][i]=f[i][j];
}
}
int ans=1;
for(register int i=1;i<=n;i++){
if(l[i][n]){
ans=max(ans,f[i][n]);
}
}
printf("%dn",ans);
return 0;
}
|
前置姿势 没有上司的舞会
这题就是舞会的一个升级版，在没有上司的舞会中，数据保证会成一棵树，而这道题中，每一名骑士都有其痛恨的骑士，我们可以理解为有n个节点，n条边，那么在这个图中必然成环。
我们此时引入一个叫做基环树的东西，你可以理解为一棵树加上了一条边，使它成环。那么一棵基环树有什么神奇的性质呢？拆掉环中一条边，其必定成树
那么我们这道题目中，我们就可以考虑每次拆去环中的一条边，使其成为一棵树，再按照没有上司的舞会那样跑一遍树形dp即可。
我们遍历每一个环，我们将该环拆开，分别用拆的点两边的节点当作根节点统计答案，因为我们此时这两个节点不能都选，我们强制要求不选根节点，取两种情况中较大的答案，即为此时这个图的答案，那么最后将所有图的答案加起来即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int read(){
int res=0,f=1;char ch=' ';
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int N=5e6+5;
long long f[N][2];
int n,fa[N];
int findf(int x){
if(fa[x]==x) return x;
else return fa[x]=findf(fa[x]);
}
int l[N],r[N],line[N],tot;
int head[N],to[N],cnt=1,nxt[N];
void qxx(int x,int y){
cnt++;nxt[cnt]=head[x];head[x]=cnt;to[cnt]=y;
}
int flag[N];
long long val[N];
void dfs(int x,int fa){
f[x][0]=0;f[x][1]=val[x];
for(register int i=head[x];i;i=nxt[i]){
int k=to[i];
if(!flag[i]&&k!=fa){
dfs(k,x);
f[x][0]+=max(f[k][1],f[k][0]);
f[x][1]+=f[k][0];
}
}
}
int main() {
n=read();
for(register int i=1;i<=n;i++) fa[i]=i;
for(register int i=1;i<=n;i++){
val[i]=read();
int x=i,y=read();
qxx(x,y);qxx(y,x);
int fx=findf(x),fy=findf(y);
if(fx!=fy) fa[fx]=fy;
else {
l[++tot]=x;r[tot]=y;line[tot]=cnt-1;
}
}
long long ans=0,sum1=0,sum2=0;
for(register int i=1;i<=tot;i++){
flag[line[i]]=flag[line[i]^1]=1;
dfs(l[i],0); sum1=f[l[i]][0];
dfs(r[i],0); sum2=f[r[i]][0];
ans+=max(sum1,sum2);
flag[line[i]]=flag[line[i]^1]=0;
}
printf("%lldn",ans);
return 0;
}
|
毒瘤蓝题，第一次发现dp的蓝题这么难做。%%%kanekik(这个神仙写的题又猛又劲)
如果稍有树型dp经验的，很容易就知道这个题需要一层一层的处理，那么该如何转移呢。
我们定义f[i] [j]表示为深度为 i 选 j 个节点一共的情况数，不难相出一共有三种情况:
1.左子树深度小于 i ,右子树深度等于 i 2.左子树深度等于 i ，右子树深度小于 i 3.左子树右子树深度都等于i
当一个子树深度小于 i 的时候，那么其深度有多种情况，我们另记一个s[i] [j]数组，表示深度小于等于 i 节点个数选择 j 的情况总数
那么转移方程就很简单了
另外，如果枚举的左右节点个数不相等时，所增加的情况应乘以2
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <bits/stdc++.h>
using namespace std;
int read(){
int res=0,f=1;char ch=' ';
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int N=1e5+5;
const int mod=9901;
int n,m;
int f[205][205],s[205][205];
int main(){
n=read();m=read();
f[1][1]=1;
for(register int i=2;i<=m;i++){
for(register int j=1;j<=n;j+=2)
for(register int k=1;k<=j-1-k;k+=2){
int x=2;
if(k==j-1-k) x=1;
f[i][j]=f[i][j]%mod+x*(s[i-2][k]*f[i-1][j-1-k]%mod+s[i-2][j-1-k]*f[i-1][k]%mod+f[i-1][j-1-k]*f[i-1][k]%mod)%mod;
}
for(register int k=0;k<=n;k++){
s[i-1][k]+=s[i-2][k]+f[i-1][k];
s[i-1][k]%=mod;
}
}
printf("%dn",f[m][n]);
return 0;
}
|
但题解中给出了另一个更巨的写法，我们只考虑以上所说的s数组，那么求n个节点k的深度我们只需要 s[n] [k]-s[n] [k-1]
并且按照乘法原理，转移方程为:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include <bits/stdc++.h>
using namespace std;
int read(){
int res=0,f=1;char ch=' ';
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int N=1e5+5;
const int mod=9901;
int n,k;
int f[205][105];
int main(){
n=read();k=read();
for(register int i=1;i<=k;i++) f[1][i]=1;
for(register int i=1;i<=k;i++){
for(register int j=3;j<=n;j+=2){
for(register int g=1;g<j;g+=2){
f[j][i]=(f[j][i]+1ll*f[g][i-1]*f[j-g-1][i-1]%mod)%mod;
}
}
}
printf("%dn",(f[n][k]-f[n][k-1]+mod)%mod);
return 0;
}
|
要预先知道这种有关游戏的题目怎么做，很显然要多看几遍题目 玩几遍游戏。
刚看到该题的时候我心中一想，这不是dp水题吗？题目中有清晰的转移方程，适当的数据范围，看起来非常的好写。那么我第一时间想出的dp方程即为:
前面这个直接转移，后面那个用背包搞一搞就行。
我快乐的打了一发，样例都没过让我感到的这题的毒瘤之处，我在此记录一下我这题吃的苦。
1.题目中给的范围为0~n-1。
2.所给的管道上下界需要加一减一，因为鸟遇到管道就死了。
3.上界为m并不会死，而下界为0却会死亡。
4.写方程转移时，需要先从之前的一个状态通过上升转移过来，然后用背包背一下，最后转移啥都不点掉下来，为此我搞了一个数组来操作。
事实证明，敲代码之前多思考还是最重要的哇，以后看到这种题还是要多考虑细节。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <bits/stdc++.h>
using namespace std;
int read(){
int res=0,f=1;char ch=' ';
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int N=10005;
int n,m,k,X[N],Y[N],dp[N],sum[N],pos[N];
int l[N],h[N],f[10005][2005],inf;
int main(){
n=read();m=read();k=read();
l[0]=1;h[0]=m;
for(register int i=0;i<=n-1;i++){
l[i]=1;h[i]=m;
X[i]=read();Y[i]=read();
}
for(register int i=1;i<=k;i++){
int x=read();pos[x]++;
l[x]=read()+1;h[x]=read()-1;
}
for(register int i=0;i<=n-1;i++) sum[i]=sum[i-1]+pos[i];
memset(f,63,sizeof(f));inf=f[0][0];
for(register int i=1;i<=m;i++) f[0][i]=0;
for(register int i=0;i<=n;i++){
for(register int j=0;j<=m;j++) dp[j]=inf;
for(register int j=l[i];j<=h[i];j++){
dp[min(m,j+X[i])]=min(dp[min(m,j+X[i])],f[i][j]+1);
}
for(register int j=1;j<=m;j++){
dp[min(m,j+X[i])]=min(dp[min(m,j+X[i])],dp[j]+1);
}
for(register int j=l[i];j<=h[i];j++){
if(j-Y[i]>0) dp[j-Y[i]]=min(dp[j-Y[i]],f[i][j]);
}
for(register int j=1;j<=m;j++){
f[i+1][j]=dp[j];
}
}
int minv=inf;
for(register int i=1;i<=m;i++){
minv=min(minv,f[n][i]);
}
if(minv==inf){
int ans=0;
for(register int i=n-1;i>=0;i--){
int judge=0;
for(register int j=1;j<=m;j++){
if(f[i][j]!=inf){
judge=1;break;
}
}
if(judge){
puts("0");
printf("%dn",sum[i]-1);
return 0;
}
}
}
puts("1");
printf("%dn",minv);
return 0;
}
|
好久没更新这个dp题目专题啦，最近写了个题，就搬到这边来水水。
很明显题目中所说的贪心思路是错误的，我们考虑区间dp，定义此时f[i] [j] [k]当前区间为i,j，并且当前点在左端点还是右端点，k=0代表的是在左端点，k=1代表的是在右端点。现在考虑转移，如果考虑每次加上一个点就加上这个点所需要的花费，花费=持续时间*当前路灯的功耗，但仔细一想，这个持续时间如果求出呢?我最先开始准备另外记下一个数组代表当前这个状态，但后来发现当前状态最优的时间不一定对后面状态最优，我们考虑其他转移。我们考虑每次这个人移动一段距离，其他未关的点总花费，这样就成功避免了时间这一毒瘤状态。
那么转移方程即为:
下面是代码啦:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <bits/stdc++.h>
using namespace std;
int read(){
int res=0,f=1;char ch=' ';
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int N=1e2+5;
int n,c,sum[N];
struct node{
int pos,val;
}t[N];
bool cmp(node a,node b){return a.pos<b.pos;}
int f[N][N][2];
int get_dis(int l,int r){
return sum[n]-sum[r]+sum[l-1];
}
int main(){
n=read();c=read();
for(register int i=1;i<=n;i++) t[i].pos=read(),t[i].val=read();
sort(t+1,t+1+n,cmp);
for(register int i=1;i<=n;i++) sum[i]=sum[i-1]+t[i].val;
memset(f,63,sizeof(f));
f[c][c][0]=f[c][c][1]=0;
for(register int len=2;len<=n;len++){
for(register int l=1;l<=n-len+1;l++){
int r=l+len-1;
f[l][r][0]=min(f[l][r][0],min(f[l+1][r][0]+(t[l+1].pos-t[l].pos)*get_dis(l+1,r),f[l+1][r][1]+(t[r].pos-t[l].pos)*get_dis(l+1,r)));
f[l][r][1]=min(f[l][r][1],min(f[l][r-1][0]+(t[r].pos-t[l].pos)*get_dis(l,r-1),f[l][r-1][1]+(t[r].pos-t[r-1].pos)*get_dis(l,r-1)));
}
}
printf("%dn",min(f[1][n][1],f[1][n][0]));
return 0;
}
|
近期评论