2014
02-27

# Travel around the world

Around the World in 80 Days is a 2004 comedy film based on Jules Verne’s novel of the same name. It stars Jackie Chan, Steve Coogan and Cécile de France. The film is set in 19th-century Britain and centers on Phileas Fogg, here reimagined as an eccentric inventor and his efforts to circumnavigate the globe in 80 days. During the trip, he is accompanied by his Chinese valet, Passepartout.

Robust is attracted by the film and planning for a tour around the world.

There are N countries in the world,and Robust has assigned each country a value Fi for friendliness to tourist.

Robust may go from country A to country B if the differences |Fa-Fb| is not bigger than M(FDL,Friendliness Difference Limit),or he would feel uncomfortable.
Robust wishes to go to each country for exactly one time.
Now he is choosing a country A to begin and a country B to end his tour(A!=B),
he wonders how many different choices he could make, ie ,how many different pairs of (A,B) that would satify Robust’s needs.

Input contains multiple cases.
Each test case starts with two integer N(2<=N<=10^4) ,M(1<=M<=10^6), indicating that there are N countries and the FDL. Follow by one lines contains N integers , the ith integer Fi(0<=Fi<=10^6) represents country i’s friendliness to tourist.

Input contains multiple cases.
Each test case starts with two integer N(2<=N<=10^4) ,M(1<=M<=10^6), indicating that there are N countries and the FDL. Follow by one lines contains N integers , the ith integer Fi(0<=Fi<=10^6) represents country i’s friendliness to tourist.

2 2
1 2
3 1
4 5 6

2
2
Hint
In sample 1,Robust ‘s travel routes may be 1->2,2->1,
the start-end pairs can be (1,2),(2,1),so the answer is 2.
In sample 2,Robust’s travel routes may be 1->2->3,3->2->1,
the start-end pairs can be (1,3),(3,1)so the answer is 2.



f[i][j]=Max( f[i-1][k]+w[k+1..j] )

f[i..j]=Max( f[i..k]+f[k+1..j]+ w[i..j] )

#include <iostream>
using namespace std;
const int maxn=1100;
int f[maxn];
int s[maxn],t[maxn],h[maxn];
int n,m;
int sta[maxn],ss;
void dp()
{
int i,j,k;
for (i=0;i<=n;i++) h[i]=f[i]+s[i]*s[i]+t[i];
sta[ss=0]=0;
k=0;
for (i=1;i<=n;i++)
{
while (ss>=1&&(h[i]-h[sta[ss]])*(s[sta[ss]]-s[sta[ss-1]])<=(h[sta[ss]]-h[sta[ss-1]])*(s[i]-s[sta[ss]])) ss–;
sta[++ss]=i;
while (k<ss&&h[sta[k+1]]-h[sta[k]]<=(s[sta[k+1]]-s[sta[k]])*2*s[i]) k++;
f[i]=h[sta[k]]-2*s[i]*s[sta[k]]+s[i]*s[i]-t[i];
}
}
int main()
{
while (scanf("%d%d",&n,&m),n||m)
{
int i,j;
s[0]=t[0]=h[0]=0;
for (i=1;i<=n;i++)
{
scanf("%d",s+i);
t[i]=t[i-1]+s[i]*s[i];
s[i]=s[i-1]+s[i];
}
f[0]=0;
for (i=1;i<=n;i++) f[i]=s[i]*s[i]-t[i];
while (m–)
dp();
printf("%d\n",f[n]/2);
}
return 0;
}

#include <iostream>
using namespace std;
const int maxn=1100,maxl=999999999;
int f[maxn],g[2][maxn];
int w[maxn][maxn];
int s[maxn],t[maxn];
int n,m;
int cw(int i,int j)
{
return (s[j]-s[i-1])*(s[j]-s[i-1])-(t[j]-t[i-1]);
}
int main()
{
while (scanf("%d%d",&n,&m),n||m)
{
int i,j,k,tp;
s[0]=t[0]=0;
for (i=1;i<=n;i++)
{
scanf("%d",s+i);
t[i]=t[i-1]+s[i]*s[i];
s[i]=s[i-1]+s[i];
}
tp=0;
for (i=1;i<=n;i++)
{
g[0][i]=0;
f[i]=cw(1,i);
}
f[0]=0;
for (i=1;i<=m;i++)
{
g[tp][n]=0;g[1-tp][n+1]=n-1;
for (j=n;j>=1;j–)
{
f[j]=maxl;
for (k=g[tp][j];k<=g[1-tp][j+1]&&k<j;k++)
if (f[j]>f[k]+cw(k+1,j))
{
f[j]=f[k]+cw(k+1,j);
g[1-tp][j]=k;
}
}
tp=1-tp;
}
printf("%d\n",f[n]/2);
}
return 0;
}

1. 加长版开头从杰森-斯坦森出场到出医院大门上车，是一个长达4分钟的长镜头连下来的，当中增添了杰森从他表弟手中拿回托雷多的项链，还给了他表弟一把微冲，而且当中没添加，加快人物镜头的特效。删减版加人物镜头特效的肯能是为了效果更好一点吧，更有紧张暴力的气氛，我下

2. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

3. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

4. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

5. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

6. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

7. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

8. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

9. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

10. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

11. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

12. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

13. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

14. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

15. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！

16. 我要把鸡脸妹那个绿毛鸡做成人彘，然后再骨醉，最后凌迟处死。【人彘自己搜，很残忍的哦，还有凌迟处死。骨醉是吧人彘放在装满酒的酒缸里，泡着】谁叫他和瑶瑶抢葳的哼！