USACO 2005 November Gold

@@@@1@@@@
水题。。。每行每列建个XX然后二分图然后最小覆盖集。。
太水不想写。。
@@@@2@@@@
DP阿。。
加入l之后。。
DP[1][l][r]目前在r。。最小的总代价。。
DP[0][l][r]目前在l。。最小的总代价。。
Ans=min(DP[0][0][n-1],DP[1][0][n-1])
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=1000+10,inf=~0U>>1;
int P[maxn];
int DP[2][maxn][maxn];
bool inQ[2][maxn][maxn]={0};
struct node
{
int d,l,r;
node(int d,int l,int r):d(d),l(l),r(r){}
};
queue<node> Q;
inline void Push(int d,int l,int r)
{
inQ[d][l][r]=true;
Q.push(node(d,l,r));
}
inline void Renew(int d,int l,int r,int c)
{
if(DP[d][l][r]>c)
{
DP[d][l][r]=c;
if(!inQ[d][l][r])
Push(d,l,r);
}
}
int n,l;
int main()
{
cin>>n>>l;
for(int i=0;i<n;i++) cin>>P[i];
P[n]=l;n++;
for(int d=0;d<2;d++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
DP[d][i][j]=inf;
sort(P,P+n);
int i=lower_bound(P,P+n,l)-P;
DP[0][i][i]=DP[1][i][i]=0;
Push(0,i,i);Push(1,i,i);
while(Q.size())
{
int d,l,r;
node c=Q.front();Q.pop();inQ[d=c.d][l=c.l][r=c.r]=false;
int cost=DP[d][l][r],num=n-(r-l+1);
if(c.d==0)
{
if(l) Renew(0,l-1,r,cost+num*(P[l]-P[l-1]));
if(r<n-1) Renew(1,l,r+1,cost+num*(P[r+1]-P[l]));
}
else
{
if(l) Renew(0,l-1,r,cost+num*(P[r]-P[l-1]));
if(r<n-1) Renew(1,l,r+1,cost+num*(P[r+1]-P[r]));
}
}
cout<<min(DP[0][0][n-1],DP[1][0][n-1])<<endl;
}@@@3@@@
???怎么没文件的。。
难道要事先搞到程序里面去?靠。。BS阿。。。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>