首页 > 代码库 > 教主泡嫦娥[有趣的dp状态设计]
教主泡嫦娥[有趣的dp状态设计]
P1342 教主泡嫦娥
时间: 1000ms / 空间: 131072KiB / Java类名: Main
背景
2012年12月21日下午3点14分35秒，全世界各国的总统以及领导人都已经汇聚在中国的方舟上。
但也有很多百姓平民想搭乘方舟，毕竟他们不想就这么离开世界，所以他们决定要么登上方舟，要么毁掉方舟。
LHX教主听说了这件事之后，果断扔掉了手中的船票。在地球即将毁灭的那一霎那，教主自制了一个小型火箭，奔向了月球……
教主登上月球之后才发现，他的女朋友忘记带到月球了，为此他哭了一个月。
但细心的教主立马想起了小学学过的一篇课文，叫做《嫦娥奔月》，于是教主决定，让嫦娥做自己的新任女友。
但也有很多百姓平民想搭乘方舟，毕竟他们不想就这么离开世界，所以他们决定要么登上方舟，要么毁掉方舟。
LHX教主听说了这件事之后，果断扔掉了手中的船票。在地球即将毁灭的那一霎那，教主自制了一个小型火箭，奔向了月球……
教主登上月球之后才发现，他的女朋友忘记带到月球了，为此他哭了一个月。
但细心的教主立马想起了小学学过的一篇课文，叫做《嫦娥奔月》，于是教主决定，让嫦娥做自己的新任女友。
描述
教主拿出他最新研制的LHX(Let‘s be Happy Xixi*^__^*)卫星定位系统，轻松地定位到了广寒宫的位置。
见到嫦娥之后，教主用温柔而犀利的目光瞬间迷倒了嫦娥，但嫦娥也想考验一下教主。
嫦娥对教主说："看到那边的环形山了么？你从上面那个环走一圈我就答应你～"
教主用LHX卫星定位系统查看了环形山的地形，环形山上一共有N个可以识别的落脚点，以顺时针1~N编号。每个落脚点都有一个海拔，相邻的落脚点海拔不同（第1个和第N个相邻）。
教主可以选择从任意一个落脚点开始，顺时针或者逆时针走，每次走到一个相邻的落脚点，并且最后回到这个落脚点。
教主在任意时刻，都会有"上升"、"下降"两种状态的其中一种。
当教主从第i个落脚点，走到第j个落脚点的时候（i和j相邻）
j的海拔高于i的海拔：如果教主处于上升状态，教主需要耗费两段高度差的绝对值的体力；否则耗费高度差平方的体力。
j的海拔低于i的海拔：如果教主处于下降状态，教主需要耗费两段高度差的绝对值的体力；否则耗费高度差平方的体力。
当然，教主可以在到达一个落脚点的时候，选择切换自己的状态（上升→下降，下降→上升），每次切换需要耗费M点的体力。在起点的时候，教主可以自行选择状态并且不算切换状态，也就是说刚开始教主可以选择任意状态并且不耗费体力。
教主希望花费最少的体力，让嫦娥成为自己的女朋友。
见到嫦娥之后，教主用温柔而犀利的目光瞬间迷倒了嫦娥，但嫦娥也想考验一下教主。
嫦娥对教主说："看到那边的环形山了么？你从上面那个环走一圈我就答应你～"
教主用LHX卫星定位系统查看了环形山的地形，环形山上一共有N个可以识别的落脚点，以顺时针1~N编号。每个落脚点都有一个海拔，相邻的落脚点海拔不同（第1个和第N个相邻）。
教主可以选择从任意一个落脚点开始，顺时针或者逆时针走，每次走到一个相邻的落脚点，并且最后回到这个落脚点。
教主在任意时刻，都会有"上升"、"下降"两种状态的其中一种。
当教主从第i个落脚点，走到第j个落脚点的时候（i和j相邻）
j的海拔高于i的海拔：如果教主处于上升状态，教主需要耗费两段高度差的绝对值的体力；否则耗费高度差平方的体力。
j的海拔低于i的海拔：如果教主处于下降状态，教主需要耗费两段高度差的绝对值的体力；否则耗费高度差平方的体力。
当然，教主可以在到达一个落脚点的时候，选择切换自己的状态（上升→下降，下降→上升），每次切换需要耗费M点的体力。在起点的时候，教主可以自行选择状态并且不算切换状态，也就是说刚开始教主可以选择任意状态并且不耗费体力。
教主希望花费最少的体力，让嫦娥成为自己的女朋友。
输入格式
输入的第一行为两个正整数N与M，即落脚点的个数与切换状态所消耗的体力。
接下来一行包含空格隔开的N个正整数，表示了每个落脚点的高度，题目保证了相邻落脚点高度不相同。
接下来一行包含空格隔开的N个正整数，表示了每个落脚点的高度，题目保证了相邻落脚点高度不相同。
输出格式
输出仅包含一个正整数，即教主走一圈所需消耗的最小体力值。
测试样例1
输入
6 7
4 2 6 2 5 6
输出
27
备注
【样例说明】
从第3个落脚点开始以下降状态向前走，并在第4个落脚点时切换为上升状态。
这样共耗费4 +(7)+3+1+2^2+2^2+4=27点体力。
【数据规模】
对于10%的数据，N ≤ 10；
对于30%的数据，N ≤ 100，a[i] ≤ 1000；
对于50%的数据，N ≤ 1000，a[i] ≤ 100000；
对于100%的数据，N ≤ 10000，a[i] ≤ 1000000，M ≤ 1000000000；
从第3个落脚点开始以下降状态向前走，并在第4个落脚点时切换为上升状态。
这样共耗费4 +(7)+3+1+2^2+2^2+4=27点体力。
【数据规模】
对于10%的数据，N ≤ 10；
对于30%的数据，N ≤ 100，a[i] ≤ 1000；
对于50%的数据，N ≤ 1000，a[i] ≤ 100000；
对于100%的数据，N ≤ 10000，a[i] ≤ 1000000，M ≤ 1000000000；
先说说网上的随机化算法优化O(n^2)暴力——>α(nlogn){常数60+}
//非常有可能被卡常，且有可能卡WA//期望得分：100 //实际得分：80-100 #include<ctime>#include<cmath>#include<cstdio>#include<cstdlib>#include<iostream>#define pf(x) ((ll)(x)*(ll)(x))#define OPT __attribute__((optimize("O2")))using namespace std;typedef long long ll;const int N=10005;ll f[N][2],ans[N];int n,m,a[N<<1],b[N],tp[30];OPT inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}OPT inline ll DP(int start){ if(ans[start]) return ans[start]; for(int cnt=0,i=start;i<=start+n;i++) b[++cnt]=a[i]; f[1][0]=f[1][1]=0; for(int i=2;i<=n+1;i++){ if(b[i]>b[i-1]){ f[i][1]=min(f[i-1][0]+m+b[i]-b[i-1],f[i-1][1]+b[i]-b[i-1]); f[i][0]=min(f[i-1][1]+m+pf(b[i]-b[i-1]),f[i-1][0]+pf(b[i]-b[i-1])); } else{ f[i][0]=min(f[i-1][1]+m+b[i-1]-b[i],f[i-1][0]+b[i-1]-b[i]); f[i][1]=min(f[i-1][0]+m+pf(b[i]-b[i-1]),f[i-1][1]+pf(b[i]-b[i-1])); } } return ans[start]=min(f[n+1][1],f[n+1][0]);}OPT int main(){ srand(time(0)); n=read();m=read(); for(int i=1;i<=n;i++) a[i+n]=a[i]=read(); for(int i=1;i<=18;i++) tp[i]=rand()%n+1; for(double T=n;T>=10;T*=0.5){ for(int i=1,now;i<=18;i++){ for(int j=1;j<=21;j++){ now=tp[i]+sin((double)(rand()%10000)/10000)*T; if(now<=0||now>n) continue; if(DP(now)>=DP(tp[i])) continue; tp[i]=now; } } } ll Ans=0x7fffffffffffffffLL; for(int i=1;i<=18;i++) Ans=min(Ans,ans[tp[i]]); cout<<Ans; return 0;}
正经算法
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#define pf(x) (1LL*(x)*(x))using namespace std;typedef long long ll;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}const int N=10005;int n,m,a[N<<1];ll f[N][2][2],Ans;void DP(){ for(int i=1;i<=n;i++){ for(int j=0;j<2;j++){ if((a[i]<a[i-1])^j){ f[i][j][0]=f[i-1][j][0]+abs(a[i]-a[i-1]); f[i][j][1]=min(f[i-1][j][1], min(f[i-1][j^1][0],f[i-1][j^1][1])+m)+abs(a[i]-a[i-1]); } else{ f[i][j][0]=f[i-1][j][0]+pf(a[i]-a[i-1]); f[i][j][1]=min(f[i-1][j][1], min(f[i-1][j^1][0],f[i-1][j^1][1])+m)+pf(a[i]-a[i-1]); } } }}int main(){ n=read();m=read(); for(int i=0;i<n;i++) a[i]=read();a[n]=a[0]; //情况1、2 memset(f,0,sizeof f);memset(f[0],0x3f,sizeof f[0]); f[0][0][0]=f[0][1][0]=0;; DP(); Ans=min(min(f[n][0][0],f[n][0][1]),min(f[n][1][0],f[n][1][1])); //情况3 memset(f,0,sizeof f);memset(f[0],0x3f,sizeof f[0]); f[0][0][0]=0; DP();Ans=min(Ans,f[n][0][1]-m); //情况3 memset(f,0,sizeof f);memset(f[0],0x3f,sizeof f[0]); f[0][1][0]=0; DP();Ans=min(Ans,f[n][1][1]-m); cout<<Ans; return 0;}
教主泡嫦娥[有趣的dp状态设计]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。