{"id":243,"date":"2010-05-08T12:27:00","date_gmt":"2010-05-08T04:27:00","guid":{"rendered":"http:\/\/localhost\/?p=243"},"modified":"2010-05-08T12:27:00","modified_gmt":"2010-05-08T04:27:00","slug":"ahoi2007_treasure_house_maze","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=243","title":{"rendered":"[AHOI2007]\u5b9d\u5e93\u8ff7\u5bab"},"content":{"rendered":"

www.rqnoj.cn\/Problem_301.html<\/a>
\u6655\u3002\u3002\u7adf\u7136\u6284TopCoder\u7684\u539f\u9898\u3002\u3002
\u770b\u4e0a\u53bb\u5f88\u96be\uff0c\u56e0\u4e3a10^10\u7684\u641c\u7d22\u662f\u8981\u60b2\u5267\u7684\u3002\u3002\u4f46\u5b9e\u9645\u4e0a\u53ea\u8981\u6bcf\u4e2a\u70b9\u4e2d\u95f4\u70b9\u5411\u5de6\u5411\u53f3\u641c\u51fa10^5\u7684\u8def\u5f84\u7136\u540e\u90fd\u6392\u5e8f\u5c31\u53ef\u4ee5\u76f4\u63a5\u626b\u63cf\u5f97\u51fa\u7ed3\u679c\u4e86\u3002\u3002
Code\uff1a
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>2,maxn=10,maxp=100000+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct Array
{
double A[maxp];int n;
void set(){n=0;}
Array(){set();}
void add(double x){A[n++]=x;}
void Sort(){sort(A,A+n);}
double operator[](int v){return A[v];}
};
int n;double D[maxn][maxn];
Array L,R;
void DfsL(int pos,int d,double now)
{
if(!d){L.add(now);return;}
rep(i,n)DfsL(i,d-1,now+D[i][pos]);
}
void DfsR(int pos,int d,double now)
{
if(!d){R.add(now);return;}
rep(i,n)DfsR(i,d-1,now+D[pos][i]);
}
int main()
{
\/\/freopen("in","r",stdin);
cin>>n;rep(i,n)rep(j,n){cin>>D[i][j];}
double ans=inf;
rep(i,n)
{
int l=n\/2,r=n-l;
L.set();R.set();
DfsL(i,l,0);DfsR(i,r,0);
L.Sort();R.add(inf);R.add(-inf);R.Sort();int j=R.n-1;
for(int i=0;i<L.n;i++)
{
while(L[i]+R[j]>=2007)j–;
ans=min(ans,2007-L[i]-R[j]);
ans=min(ans,L[i]+R[j+1]-2007);
}
}
printf("%0.2lfn",ans);
} <\/p>\n","protected":false},"excerpt":{"rendered":"

www.rqnoj.cn\/Problem_301.html\u6655\u3002\u3002\u7adf\u7136\u6284TopCoder\u7684\u539f\u9898\u3002\u3002\u770b\u4e0a\u53bb\u5f88\u96be\uff0c\u56e0\u4e3a10^10\u7684\u641c\u7d22\u662f\u8981\u60b2\u5267\u7684\u3002\u3002\u4f46\u5b9e\u9645\u4e0a\u53ea\u8981\u6bcf\u4e2a\u70b9\u4e2d\u95f4\u70b9\u5411\u5de6\u5411\u53f3\u641c\u51fa10^5\u7684\u8def\u5f84\u7136\u540e\u90fd\u6392\u5e8f\u5c31\u53ef\u4ee5\u76f4\u63a5\u626b\u63cf\u5f97\u51fa\u7ed3\u679c\u4e86\u3002\u3002Code\uff1a#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backconst int inf=~0U>>2,maxn=10,maxp=100000+10;using namespace std;typedef long long ll;typedef unsigned long long ull;struct Array{ double A[maxp];int n; void set(){n=0;} Array(){set();} void add(double x){A[n++]=x;} void Sort(){sort(A,A+n);} double operator[](int v){return A[v];}};int n;double D[maxn][maxn];Array L,R;void DfsL(int pos,int d,double now){ if(!d){L.add(now);return;} rep(i,n)DfsL(i,d-1,now+D[i][pos]);}void DfsR(int pos,int d,double now){ if(!d){R.add(now);return;} rep(i,n)DfsR(i,d-1,now+D[pos][i]);}int […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/243"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=243"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/243\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=243"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=243"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=243"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}