poj1925Spiderman(dp)

确实是破题按复杂度估计怎么着也不能按坐标D 啊

网上的代码交上去还TLE 无语了多次TLE之后终于看到一次WA。。好高兴

以横坐标进行DP dp[j] = min(dp[j],dp[2*x[i]-j]+1) 这个2*x[i]-j其实是 j+2*(x[i]-j]) 由当前坐标可以由没跳这个个建筑物i之前的坐标推来

限制条件为 (j-x[i]）*（j-x[i])+(y[i]-y[1])*(y[i]-y[1])>y[i]*y[i];

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cstring>

 #include<stdlib.h>

 using namespace std;

 #define N 5010

 #define M 2000010

 #define INF 0xfffffff

 #define LL long long

 int dp[M];

 LL x[N],y[N];

 int main()

 {

     int i,j,k,n;

     scanf("%d",&k);

     while(k--)

     {

         scanf("%d",&n);

         for(i = ; i <= n ; i++)

         scanf("%lld%lld",&x[i],&y[i]);

         for(i = ; i <= M ; i++)

         dp[i] = INF;

         dp[x[]] = ;

         int ans = INF;

         for(i =  ; i <= n ; i++)

         {

             LL s1 = (y[i]-y[])*(y[i]-y[]);

             for(j = x[i] ; ; j++)

             {

                 LL s2 = (j-x[i])*(j-x[i]);

                 if(s2+s1>y[i]*y[i])

                 {

                     break;

                 }

                 if(*x[i]-j>=x[])

                 dp[j] = min(dp[*x[i]-j]+,dp[j]);

                 else

                 break;

                 if(j>=x[n])

                 ans = min(ans,dp[j]);

             }

         }

         if(ans==INF)

         printf("-1\n");

         else

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

poj1925Spiderman(dp)

最新文章

热门文章