10.17 校内模拟赛（火炬torch、硬币游戏xoinc、过路费toll|USACO）

题目及数据：http://pan.baidu.com/s/1bn0DEUF

T1:火炬torch

由于N*M得到的数只由0、1两种数组成，不难想到用二进制来模拟N*M，数据太弱就A了。。

T2:硬币游戏xoinc

典型的博弈dp。记dp(x,y)表示还剩下x个可以选，对手上一轮选了y个。那么你的状态即是dp[x-k][k]（1<=min(2y,x) )

则为满足两人都按最优方案决策，则由dp[x][y]=max{sum[x]-dp[x-k][k]}；不难发现,这个dp是 2d/1d的，显然不能满足2000的数据量

进一步，dp[x][y]=sum[x]-dp[x-k][k] , 1<=k<=min（2y,x) dp[x][y-1]=sum[x]-dp[x-k][k]，1<=k<=min(2y-2,x)

不难发现前者只比后者多了两种状态,也就是意味着这个dp可以优化成2d/0d

于是 dp[x][y]=max(dp[x][y-1],max(sum[x]-dp[x-2y][2y],sum[x]-dp[x-2y+1][2y-1]));

T3:过路费toll

比较好的最短路径的题。由于每次松弛时，附带的最大点费用不是始终确定的，所以一般的直接最短路算法是不能胜任的。

由于N<=250，且是多源最短路径，考虑Floyd。

由于floyd的枚举媒介节点k的性质，可以将k节点按点费用从大到小排序，那么floyd恰好完全正确。

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<cmath>
 5 #include<cstdio>
 6 #include<cstdlib>
 7 #include<cstring>
 8 #include<iostream>
 9 #include<algorithm>
10 using namespace std;
11 const int N = 100010;
12 #define For(i,n) for(int i=1;i<=n;i++)
13 #define Rep(i,l,r) for(int i=l;i<=r;i++)
14 
15 int j,t,n,A[N];
16 long long s;
17 
18 int main(){
19     freopen("torch.in","r",stdin);
20     freopen("torch.out","w",stdout);
21     scanf("%d",&n);
22     For(i,N*2){
23         t=i;s=0;
24         while(t){
25             A[++A[0]]=t%2;
26             t/=2;
27         }
28         while(A[0]>0)  s=s*10+A[A[0]--];
29         if(s%n) continue;
30         else    {
31             cout<<s/n<<endl;
32             return 0;
33         }
34     }
35     puts("No Solution");
36     return 0;
37 }

torch

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<cmath>
 5 #include<cstdio>
 6 #include<cstdlib>
 7 #include<cstring>
 8 #include<iostream>
 9 #include<algorithm>
10 using namespace std;
11 const int N = 2010;
12 #define For(i,n) for(int i=1;i<=n;i++)
13 #define Rep(i,l,r) for(int i=l;i<=r;i++)
14 
15 int sum[N],A[N],opt[N][N],n;
16 
17 void init(){
18     scanf("%d",&n);
19     For(i,n)  scanf("%d",&A[n-i+1]);
20     For(i,n)  sum[i]=sum[i-1]+A[i];
21 }
22 
23 void DP(){
24     For(i,n)
25       For(j,n){ 
26           opt[i][j]=max(opt[i][j],opt[i][j-1]);
27           if(i>=j*2)   opt[i][j] = max(opt[i][j],sum[i]-opt[i-2*j][2*j]);
28           if(i>=j*2-1) opt[i][j] = max(opt[i][j],sum[i]-opt[i-(2*j-1)][2*j-1]);
29        }
30     printf("%d
",opt[n][1]);
31 }
32 
33 int main(){
34     init();
35     DP();
36     return 0;
37 }

xoinc

 1 #include<set>
 2 #include<map>
 3 #include<cmath>
 4 #include<queue>
 5 #include<vector>
 6 #include<cstdio>
 7 #include<cstdlib>
 8 #include<cstring>
 9 #include<iostream>
10 #include<algorithm>
11 using namespace std;
12 const int N = 300;
13 #define For(i,n) for(int i=1;i<=n;i++)
14 #define Rep(i,l,r) for(int i=l;i<=r;i++)
15 #define Down(i,r,l) for(int i=r;i>=l;i--)
16 
17 int c[N],cost[N][N],dis[N][N];
18 int id[N],x,y,w,n,m,k;
19 
20 void init(){
21     freopen("toll.in","r",stdin);
22     freopen("toll.out","w",stdout);
23     scanf("%d%d%d",&n,&m,&k);
24     memset(dis,0x777777f,sizeof(dis));
25     For(i,n) {
26         id[i]=i;
27         scanf("%d",&c[i]);
28         dis[i][i]=0;
29     }
30     For(i,m){
31         scanf("%d%d%d",&x,&y,&w);
32         dis[x][y]=min(dis[x][y],w);dis[y][x]=dis[x][y];
33     }
34 }
35 
36 bool cmp(int A,int B){
37     return c[A]<c[B];
38 }
39 
40 int Max(int a,int b,int c){return max(max(a,b),c);}
41 
42 void Floyd(){
43     memset(cost,0x7777777f,sizeof(cost));
44     For(k,n){
45         int cur=id[k];
46         For(i,n)
47           For(j,n)
48             if(dis[i][cur]<=dis[i][j]-dis[cur][j]){
49                 dis[i][j]=dis[i][cur]+dis[cur][j];
50                 if(cost[i][j]>dis[i][j]+Max(c[i],c[cur],c[j]))
51                 cost[i][j]=dis[i][j]+Max(c[i],c[cur],c[j]);
52             }
53     }
54 }
55 
56 int main(){
57     init();
58     sort(id+1,id+n+1,cmp);
59     Floyd();
60     For(i,k){
61         scanf("%d%d",&x,&y);
62         printf("%d
",cost[x][y]);
63     }
64     return 0;
65 }

toll