C -- 图论你先敲完模板
Time Limit：5s Memory Limit：256MByte
Submissions：660Solved：160
DESCRIPTION
今天HHHH在操场上跑步,HHHH作为一个爱运动的人,肯定会想方设法把跑步所消耗的能量减到最少.
现在这个操场上有nn个可以休息的点,他们的坐标分别为x1,x2...xn(xi≤xi+1)x1,x2...xn(xi≤xi+1),HHHH刚开始在 x1x1 ,并且他只能在这些点休息,在中途不能停下来,否则会因为旁边的音浪太强而被晃到.
如果HHHH连续跑一段长度为ll的距离,那么他将会消耗2l+a2l+a的能量(aa为HHHH的可爱值)
现在给你这些点的坐标,请帮HHHH计算他跑到xnxn点所需要消耗的能量最少是多少.
INPUT
第一行是一个整数
T(1≤T≤10)T(1≤T≤10),表示有
TT组数据对于每组数据输入一行2个整数
n,a (1≤n≤105,1≤a≤106)n,a (1≤n≤105,1≤a≤106)表示总共有
nn个休息点,
HHHH的可爱值为
aa.接着一行
nn个数
x1,x2...,xn(0≤xi≤3×106,0≤xi+1−xi≤30)x1,x2...,xn(0≤xi≤3×106,0≤xi+1−xi≤30),表示点的位置.
OUTPUT
每组数据输出一行,一个整数,表示最小需要花费的体力
HINT
对于第一组样例,最少的体力消耗是先从3跑到5,消耗6点体力,再从5跑到7,消耗6点体力,共12点 对于第二组样例,最少的体力消耗是直接从3跑到7,消耗26点体力.
思路：
很简单的dp，设定dp【i】表示走到点i的最小花费，那么对应转移：
dp【i】=min（dp【i】，dp【j】+花费）【1<=j<=i】，直接跑肯定是要超时而且数据要爆long long int的，
观察到数据范围xi-xi-1<=30. 而且a<=1e6.
所以我们只要保证x【i】-x【j】<=40以内的都可以转移一下，既不会爆long long ，又稳妥。
否则就不用转移了，因为肯定不能通过更远的点来得到更优。
Ac代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long int
ll dp[150000];
ll x[150000];
ll poww[150];
void init()
{
memset(poww,0,sizeof(poww));
poww[1]=1;
for(int i=2;i<=40;i++)
{
poww[i]=poww[i-1]*2;
}
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--)
{
int n;
ll a;
scanf("%d%lld",&n,&a);
for(int i=1;i<=n;i++)scanf("%lld",&x[i]);
dp[1]=0;
for(int i=2;i<=n;i++)
{
dp[i]=1000000000000000000;
ll Len=0;
for(int j=i-1;j>=1;j--)
{
Len+=x[j+1]-x[j];
if(Len<=40)
{
ll tmp=2;
dp[i]=min(dp[i],dp[j]+poww[Len]*tmp+a);
}
else break;
}
}
printf("%lld\n",dp[n]);
}
}
