首页 > ACM题库 > HDU-杭电 > HDU 3012-Travel around the world-动态规划-[解题报告]HOJ
2014
02-27

HDU 3012-Travel around the world-动态规划-[解题报告]HOJ

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.

Cut Pyramid

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.

题目链接

两种方法都可以用,斜率优化是可以证明的,但是Lost大神和七弦桐都说是四边形不等式,于是第一次写四边形不等式。完全没有头绪,那两个界,上界就是斜率优化的结果,下界完全是经验得来的,而且这题的方程和论文里的区间套的方程模型完全不一样

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] )

正在研究ing 哪位大神指点一下迷津吧!感谢先~

斜率优化代码

#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;
}

参考:http://hi.baidu.com/lccycc_acm/item/cdd5885e214358474eff20a1