当前位置: 代码迷 >> 综合 >> JZOJ 1281.旅行
  详细解决方案

JZOJ 1281.旅行

热度:69   发布时间:2024-01-28 16:55:15.0

很直接的想法是枚举每个二进制状态,并比较得出最小值,期望得分20分。
但是我们可以从数据范围看出这是一个二维dp (不要问我是怎么看出来的) 。考场尚未推出状态转移方程,考后参考别人的程序才想出,这其实是一道dp好题。
定义f[ i i ][0]为第 i i 个值不与后面的交换消耗的最小体力,f[ i i ][1]为第 i i 个值与后面交换消耗的最小的最小体力,sum[ i i ]为未交换时消耗的体力。
状态转移方程:
1.当第 i i 个值不与后面的值交换时,此时消耗的最小体力就是 m i n min
(第 i + 1 i+1 个值不与后面交换时的最小体力加上第 i i 个值与 i + 1 i+1 个值的差值的绝对值,
i + 1 i+1 个值与后面交换时的最小体力加上第 i i 个值与 i + 2 i+2 个值的差值的绝对值)。
code:

f[i][0]=min(f[i+1][0]+abs(a[i+1]-a[i]),f[i+1][1]+abs(a[i+2]-a[i]));

2.当第 i i 个值与后面的值交换时,此时消耗的最小体力就与第 i i 个值具体被换到哪里有关。设第 j j 个值与第 i i 个值交换,此处较难理解,用图片具体说明:
i与j交换前:
i与j交换前
i与j交换后:
i与j交换后
这里简单地用 i i 表示a[ i i ]的值(其他依次类推)。设第 i i 个位置的值与第 i i 个位置的值交换,交换后消耗的最小体力其实就是a[ j j ]与a[ i i ]的差值的绝对值加上第 i + 1 i+1 个位置和第 j j 个位置中间的差值再加上一个类似于f[ j j ][0]的式子,只是这里因为原来a[ j j ]的位置现在是a[ i i ],所以将f[ j j ][0]式子中的 j j 换成 i i 。特别的,与第 n n 个值交换,因为f[ n n ][0]和f[ n n ][1]都是0,所以f[ i i ][0]可直接由a[ n n ]与a[ i i ]的差值的绝对值加上第 i + 1 i+1 个位置和第 n n 个位置中间的差值得到。
code:

for(ll j=i+1;j<=n-1;j++)f[i][1]=min(f[i][1],min(f[j+1][0]+abs(a[i]-a[j+1]),f[j+1][1]+abs(a[i]-a[j+2]))+sum[j]-sum[i+1]+abs(a[i]-a[j]));
f[i][1]=min(f[i][1],sum[n]-sum[i+1]+abs(a[n]-a[i]));

完整code:

#include<bits/stdc++.h>
#define ll long long
#define R register
using namespace std;
inline ll read(){ll f=0,pa=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')pa=-1;ch=getchar();}while(ch>='0'&&ch<='9'){f=(f<<3)+(f<<1)+(ch^48);ch=getchar();}return f*pa;
}
inline void write(ll x){if(x<0)x=-x,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');
}
ll n,a[2005],sum[2005],f[2005][2],cha;
inline ll abss(ll a){return a>=0?a:-a;}
inline ll minn(ll a,ll b){return a>b?b:a;}
int main(){n=read();for(R ll i=1;i<=n;i++){a[i]=read();f[i][1]=f[i][0]=0x7fffffff;sum[i]=sum[i-1]+abss(a[i]-a[i-1]);}f[n][0]=f[n][1]=0;a[n+1]=a[n];for(R ll i=n-1;i>=1;i--){f[i][0]=minn(f[i+1][0]+abss(a[i+1]-a[i]),f[i+1][1]+abs(a[i+2]-a[i]));for(R ll j=i+1;j<=n-1;j++)f[i][1]=minn(f[i][1],minn(f[j+1][0]+abss(a[i]-a[j+1]),f[j+1][1]+abss(a[i]-a[j+2]))+sum[j]-sum[i+1]+abss(a[i]-a[j]));f[i][1]=minn(f[i][1],sum[n]-sum[i+1]+abss(a[n]-a[i]));}write(minn(f[1][0],f[1][1]));return 0;
}

p.s. 听说自己手写函数会比调用自带的函数跑得快,建议各位自己手写函数(虽然这题没必要)。