USACO 3.3

  • 骑马修栅栏 Riding the Fences
  • 商店购物 Shopping Offers
  • 亚瑟王的宫殿 Camelot (先晾着)
  • 家的范围 Home on the Range
  • 游戏 A Game

p2731 骑马修栅栏 Riding the Fences

欧拉回路模板题。

关于是否存在欧拉回路:
无向图:一个点的度数(连的边的条数)如果为奇数,那么这个点为奇点。一个连通的无向图,若有0个或者2个奇点,则存在欧拉回路。如果是0个奇点,从任意一个点出发都能回到该点。如果是2个奇点,从其中一个奇点出发能够到达另一个奇点。
有向图:0个或者2个点出度不等于入度的,即存在欧拉回路。
话说只有一个点出度不等于入度的图是画不出来的。设出边为n,所以入边为n。即出边条数等于入边条数。若其他点的出度均等于入度,那么该点的出度也只可能为入度。
框架:

1
2
3
4
5
6
7
8
9
10
11
12
void euler(int u)
{
for(int i=1;i<=n;i++)
if (a[u][i]>0)//还有边
{
printf("%d %d\n",u,i);
//打印顺序如果是逆序的则改成将u,i压入栈。
a[u][i]--;//没走的边的条数-1
a[i][u]--;//有向图的话就不要这一句
euler(i);
}
}

扯回这题。两顶点间可能有多个栅栏,于是我们就要统计2个点之间的栅栏条数(好坑啊)。注意:输出的话是输出最小的。然后打印的时候注意一点就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
ID: ylx14274
PROG: fence
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int m,n,u,v,k;
int i,j;
int a[501][501];//存边的
int s[501];
stack<int> t;
void euler(int u)
{
int v;
for (v=1;v<=n;v++)
if (a[u][v]>=1)//有没搜过的边
{
a[u][v]--;//标记
a[v][u]--;//双向边就都要标记
euler(v);//继续搜
}
t.push(u);//压入栈中
return;
}
int main()
{
freopen("fence.in","r",stdin);
freopen("fence.out","w",stdout);
scanf("%d\n",&m);
for (i=1;i<=m;i++)//读入边
{
scanf("%d%d",&u,&v);
a[u][v]++;//加边条数
a[v][u]++;//这是双向边
s[u]++;//存边的条数的,用来确定起点的。
s[v]++;
n=max(n,u);
n=max(n,v);//n:节点数
}
k=0;//标记
for (i=1;i<=n;i++)
if (s[i]%2==1)//最小的奇点
{
k=i;//标记
break;//跳出
}
if (k==0)//如果没奇点
{
for (i=1;i<=n;i++)
if (s[i]>0)//找到最小的有边的点
{
k=i;//标记
break;//跳出
}
}
euler(k);//从k点开始求
do
{
printf("%d\n",t.top());
t.pop();
} while (!t.empty());//倒着输出
return 0;
}

p2732 商店购物 Shopping Offers

嗯。竟然是完全背包的题。
我们为了方便处理,于是将单独购买也当做一种组合。
然后就可以放代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

/*
ID: ylx14274
PROG: shopping
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
int n;//优惠方案总数
int i,j,k,l,m,z;
struct haha
{
int n;//n 种商品组成
int k[6];//数量
int p;//优惠价
}a[200];//我们把单独购买的商品也当做一种组合
int nn;//需要购买的商品数
int d[1000];//存商品标号的,反正最多5种商品
int t;
int ai,bi,ci;
int f[6][6][6][6][6];//dp用的数组
int x[6];//存每种商品需要的数量
using namespace std;
int main()
{
freopen("shopping.in","r",stdin);
freopen("shopping.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&a[i].n);//读入商品数量
for (j=1;j<=a[i].n;j++)
{
scanf("%d%d",&ai,&bi);//ai:编号
if (d[ai]==0)//此商品没出现过
{
t++;
d[ai]=t;//存编号
}
a[i].k[d[ai]]=bi;//存组合i所需的第ai种物品的数量
}
scanf("%d",&a[i].p);//读入优惠价
}//才读完优惠方案
scanf("%d",&nn);//读入需要购买的商品数
for (i=1;i<=nn;i++)
{
scanf("%d%d%d",&ai,&bi,&ci);//ai:编号,bi:需要数量
if (d[ai]==0)//此商品没出现过
{
t++;
d[ai]=t;//存编号
}
x[d[ai]]=bi;//需求量。
n++;//组合数+1
a[n].n=1;//把零售也当成一种组合存进去
a[n].k[d[ai]]=1;//数量
a[n].p=ci;//价格
}
for (i=0;i<=5;i++)
for (j=0;j<=5;j++)
for (k=0;k<=5;k++)
for (l=0;l<=5;l++)
for (m=0;m<=5;m++)
f[i][j][k][l][m]=233333;//只能人工赋初值。
f[0][0][0][0][0]=0;//初始化
for (z=1;z<=n;z++)//n种方案,嗯,完全背包
for (i=a[z].k[1];i<=x[1];i++)
for (j=a[z].k[2];j<=x[2];j++)
for (k=a[z].k[3];k<=x[3];k++)
for (l=a[z].k[4];l<=x[4];l++)
for (m=a[z].k[5];m<=x[5];m++)
f[i][j][k][l][m]=min(f[i][j][k][l][m],
f[i-a[z].k[1]]
[j-a[z].k[2]]
[k-a[z].k[3]]
[l-a[z].k[4]]
[m-a[z].k[5]]
+a[z].p);//动态转移方程
printf("%d\n",f[x[1]][x[2]][x[3]][x[4]][x[5]]);//输出
return 0;
}

p2733 家的范围 Home on the Range

这题是dp。
状态定义:f[i][j]为以(i,j)为右下角顶点的正方形的最大边长。
边界:f[i][j]为初始读入的矩阵。
状态转移方程: f[i][j]=min{ f[i-1][j] , f[i][j-1] , f[i-1][j-1] } + 1;所以写出来其实是:如果 f[i-1][j] , f[i][j-1] , f[i-1][j-1],f[i][j]等于当前求的边长-1,才能组成一个正方形
解析: G[i-1][j] , G[i][j-1] , G[i+1][j+1]分别为(i,j)向上、向左、向左上一格的状况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
ID: ylx14274
PROG: range
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int n,i,j,k;
char c;
int f[251][251];
int sum[251];
int main()
{
freopen("range.in","r",stdin);
freopen("range.out","w",stdout);
scanf("%d\n",&n);
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
scanf("%c",&c);//读入
if (c=='1') f[i][j]=1;//标记
}
scanf("\n");
}//f[i][j]表示右下角角顶点为(i,j)的正方形最大边长
for (k=2;k<=n;k++)//枚举正方形的大小
for (i=n;i>=1;i--)
for (j=n;j>=1;j--)
if (f[i-1][j]+f[i][j-1]+f[i-1][j-1]+f[i][j]==(k-1)*4)
//其实相当于这四个点都能组成变成为k-1的正方形(都等于k-1)
{
f[i][j]++;//更大的方形
sum[k]++;//统计
}
for (i=2;i<=n;i++)
{
if (sum[i]!=0)
{
printf("%d %d\n",i,sum[i]);
}//else break;//否则更大的方形也不会有了
}
return 0;
}

p2734 游戏 A Game

经典的区间型动态规划的题。
状态只有2种:从左边拿和从右边拿。
假设当前状态a1,a2,a3,a4,a5,如果第一个人选最左边的,则问题转化为四个数a2,a3,a4,a5,然后第二个人先选,由于题目说第二个人方案也最优,所以选的也是最优方案,即f[i+1][j];先选右边同理。
f[i][j]表示i~j区间段第一个人选的最优方案。
所以dp转移方程为:f[i][j]=max{ sum[i+1][j]-f[i+1][j]+ai,sum[i][j-1]-f[i][j-1]+aj }
sum[i][j]其实就等于sum[1][j]-sum[1][i-1],于是我们用一个s数组,s[i]表示前1~i个数的和,就好了。
所以dp转移方程也可写成f[i][j]=max((s[j]-s[i-1])-f[i+1][j],(s[j]-s[i-1])-f[i][j-1]);
根据dp转移方程我们可以发现,要得到状态f[i][j],必须要得到状态f[i+1][j]和f[i][j-1]。然后我们就可以写出程序了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
ID: ylx14271
PROG: game1
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int n,i,j;
int a[101];//存数
int f[101][101];
//f[i][j]表示取i~j这个区间段player1最高得分
int s[101];//s[i]表示a[1]~a[i]的和
int main()
{
freopen("game1.in","r",stdin);
freopen("game1.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);//读入 s
s[i]=s[i-1]+a[i];//求和
f[i][i]=a[i];//初始化
}
//表示a[i]~a[j]的和的方法:s[j]-s[i-1]
for (i=n-1;i>=1;i--)
for (j=i+1;j<=n;j++)
f[i][j]=max((s[j]-s[i-1])-f[i+1][j],
(s[j]-s[i-1])-f[i][j-1]);
printf("%d %d\n",f[1][n],s[n]-f[1][n]);
return 0;
}