浙江中医药暑期训练赛四

Problem K: 背包

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 193  Solved: 102

[Submit][Status][Web Board]

Description

你有一个神奇的背包，他的容积是m(0

Input

第一行 n,m

第二行 n个数字

Output

输出方案数

Sample Input

3 40

20 20 20

Sample Output

3

#include 
using namespace std;
int n, m, a[30], ans = 0;
void dfs(int ok, int k)
{if (ok == 0)//判断边间，如果ok等于0，那说明背包正好装满了，那么这是一种装法，所以ans++;{ans++;return;}if (ok<0 || k>n)//如果要装进去的东西太多了或者所有东西都装进去了（本题必须要装满才能拿），都不满足return;dfs(ok - a[k], k + 1);//放进一个a[k]的东西dfs(ok, k + 1);//继续推进，进入下一层递归return;
}int main()
{while (~scanf("%d%d", &n, &m)){for (int i = 1; i <= n; i++)scanf("%d", &a[i]);ans = 0;dfs(m, 1);printf("%d\n", ans);}return 0;}

Problem L: 造围栏

Description

在那，山地那边，海地那边，n*m的格子里面有k匹草泥马。学名曰羊驼。LLL非常喜欢骑马，所以他就想偷至少一匹泥马，如果他骑马逃出了n*m的格子就代表偷马成功，他可以驾驭任何一匹泥马。每个回合内LLL可以驾驭他的泥马往上下左右任意地方移动一格。而牧马人JJJ发现有人在偷他的马，所以就想造围栏把泥马围在n*m的格子里面，每个回合内JJJ可以造一个围栏。现在假设两个人都采取最佳的策略，LLL先下手，问最后LLL是否得手

Input

多组测试数据

第一行输入n，m ，k (1<=n,m<=100, 0<=,k<=100,)

接下来k行每行输入x,y。表示每只神兽的位置(1<=x<=n,1<=y<=m)

Output

成功输出YES。

否则输出NO。

Sample Input

2 2 1

1 2

3 4 0

100 50 2

50 25

50 25

Sample Output

YES

NO

NO

思路

在偷羊贼赶到边界前需要在各个角落围上一边。

#include
#include
int main () {int a[101][2],n,m,k;while(~scanf("%d%d%d",&n,&m,&k)) 
{int x=0;if(k==0)printf("NO\n");else{for(int i=1;i<=k;i++) scanf("%d%d",&a[i][0],&a[i][1]);for(int i=1;i<=k;i++) {if(a[i][0]<=5){printf("YES\n");x=1;break;}if((n-a[i][0])<=4) {printf("YES\n");x=1;break;}if(a[i][1]<=5) {printf("YES\n");x=1;break;}if((m-a[i][1])<=4) {printf("YES\n");x=1;break;}}if(x==0) printf("NO\n");}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！