注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ2137Cowties题解  

2014-03-21 20:12:20|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                      cowties
                                             BY   LGS
题目大意:给你N头牛,每头牛可以在K个位置任意一个位置吃草,求每个奶牛在规定的一个位置吃草时所围成的周长最大。

题解:一看便是DP嘛,F[I][J]表示第i头牛在第j个位置的最短连接方案。i从1到N循环方程:F[I][J]=MIN(F[I][J],F[I-1][K]+dis(k,j));然而光是这样还是不能过,仔细思考后,发现了BUG。1到N是可以保证最优,而N到1最后的处理并不是累似的DP。因为比方1头奶牛有2个位置1号、2号。而2奶牛有1个位置,3奶牛有1个位置。假设目前到了F[3][1]的最优方案是1站在1号位置,2站在唯一的位置,3也是。而可能3再到2比3到1更优,那么我这个程序就选择了路线是:1-1-1-2。明显和一开始3配1矛盾。所以他们必须是强制匹配。用B[I][J]表示是由1的几号位推过来了。
然而这样还是不能过,在SYF的前车之鉴下,我知道了由于我强制匹配N-1,可能无法保证了这个方案一定最优,所以必须要在外面再加个循环,枚举起点1-n即可。而后AC。

总结:DP+思维锻炼。多方面考虑。
代码:
#include<cstdio>
#include<cmath>
#include<cstring>
#define maxn 400
#define maxx 99999999
using namespace std;
int i,j,l,n,o,m,k,t[maxn],x[maxn][maxn],y[maxn][maxn],uu[maxn][maxn];
double f[maxn][maxn],ans;
double min(double a, double b){return (a>b)?b:a;}
double dis(int a,int d,int b,int c)
 {
 int u=(x[a][b]-x[d][c]);
 int uu=(y[a][b]-y[d][c]);
 return ((double) (sqrt(u*u+uu*uu)));
 }
int main()
{
 scanf("%d",&n);
 for (i=1;i<=n;i++)
  {
  scanf("%d",&t[i]);t[i+n]=t[i];
  for (j=1;j<=t[i];j++)
          {scanf("%d%d",&x[i][j],&y[i][j]);
           x[i+n][j]=x[i][j];y[i+n][j]=y[i][j];
          }
  }
 ans=maxx;
for (o=1;o<=n;o++){    
for (i=1;i<=300;i++)
 for (j=1;j<=300;j++) f[i][j]=maxx;
 
for (i=1;i<=t[o];i++)
       {f[o][i]=0;uu[o][i]=i;}
       
for (i=o+1;i<=o+n-1;i++)
 for (j=1;j<=t[i];j++)
  for (k=1;k<=t[i-1];k++)if (f[i-1][k]!=maxx){
        double w;
        w=(double)(f[i-1][k]+dis(i,i-1,j,k));
          if (w<f[i][j]) {f[i][j]=w;uu[i][j]=uu[i-1][k];}
                                             }
 for (i=1;i<=t[o+n-1];i++)
  for (j=1;j<=t[o];j++)
     if (uu[o+n-1][i]==j) ans=min(ans,(double)(f[o+n-1][i]+dis(o+n-1,o,i,j)));
                  }
printf("%d",(int)(ans*100));
return 0; 
}
  评论这张
 
阅读(34)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018