foj 1416 飞机加油问题

http://acm.fzu.edu.cn/problem.php?pid=1416

非常赤裸的dp,

说实话看到n(n<=400,000),

用dp心里一点底都没有,

结果竟然968ms过了, 囧

#include<iostream>
#include<algorithm>
using namespace std;
int a[400000],dp[400001];
int main()
{
	int n,s,i,j,tmp;
	while(scanf("%d%d",&n,&s)!=EOF)
	{
		for(i=0;i<n;i++)
			scanf("%d",&dp[i]);
		sort(dp,dp+n);
		a[1]=dp[0];
		for(i=1,j=2;i<n;i++)
		{
			if(dp[i]!=dp[i-1])
				a[j++]=dp[i];
		}
		n=j-1;
		dp[1]=s+a[1]*a[1];
		for(i=2;i<=n;i++)
		{
			dp[i]=s+a[i]*a[i];
			for(j=1;j<i;j++)
			{
				tmp=s+(a[i]-a[j])*(a[i]-a[j])+dp[j];
				if(tmp<dp[i])
					dp[i]=tmp;
			}
		}
		printf("%d/n",dp[n]);
	}
	return 0;
} 

ps: 看status有人350ms过, 应该是存在0(n)的贪心

再发个今天用hash剔重复的YY代码

#include<iostream>   
#include<algorithm>   
using namespace std;   
int a[400000],dp[400001];
bool flag[40000];   
int main()   
{   
    int n,s,i,j,tmp;   
    while(scanf("%d%d",&n,&s)!=EOF)   
    {   
		memset(flag,0,sizeof(flag));
		j=0;
        for(i=0;i<n;i++)   
		{
            scanf("%d",&tmp);   
			if(!flag[tmp])
			{
				flag[tmp]=1;
				a[j++]=tmp;
			}
		}
        sort(a,a+j);   
        n=j-1;   
        dp[1]=s+a[1]*a[1];   
        for(i=2;i<=n;i++)   
        {   
            dp[i]=s+a[i]*a[i];   
            for(j=1;j<i;j++)   
            {   
                tmp=s+(a[i]-a[j])*(a[i]-a[j])+dp[j];   
                if(tmp<dp[i])   
                    dp[i]=tmp;   
            }   
        }   
        printf("%d/n",dp[n]);   
    }   
    return 0;   
}