【深基7.例1】距离函数

题目描述

给出平面坐标上不在一条直线上三个点坐标 $(x_1,y_1),(x_2,y_2),(x_3,y_3)$，坐标值是实数，且绝对值不超过 100.00，求围成的三角形周长。保留两位小数。

对于平面上的两个点 $(x_1,y_1),(x_2,y_2)$，则这两个点之间的距离 $dis=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$

输入格式

输入三行，第 $i$ 行表示坐标 $(x_i,y_i)$，以一个空格隔开。

输出格式

输出一个两位小数，表示由这三个坐标围成的三角形的周长。

样例 #1

样例输入 #1

0 0
0 3
4 0
1
2
3

样例输出 #1

12.00
1

提示

数据保证，坐标均为实数且绝对值不超过 $100$，小数点后最多仅有 $3$ 位。

解题思路

• 1）用两点间距离公式计算出三边长度。
• 2）计算并输出周长，记得输出格式为二位小数。

参考代码

#include
using namespace std;
int main()
{
    double a,b,c,d,e,f;
    double s1,s2,s3;
	cin>>a>>b>>c>>d>>e>>f;
	s1=sqrt((a-c)*(a-c)+(b-d)*(b-d));
	s2=sqrt((a-e)*(a-e)+(b-f)*(b-f));
	s3=sqrt((c-e)*(c-e)+(d-f)*(d-f));
	printf("%.2lf",s1+s2+s3);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

[USACO1.5]八皇后 Checker Challenge

题目描述

一个如下的 $6\times 6$ 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 $246135$ 来描述，第 $i$ 个数字表示在第 $i$ 行的相应位置有一个棋子，如下：

行号 $123456$

列号 $246135$

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 $3$ 个解。最后一行是解的总个数。

输入格式

一行一个正整数 $n$，表示棋盘是 $n\times n$ 大小的。

输出格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

样例 #1

样例输入 #1

6
1

样例输出 #1

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
1
2
3
4

提示

【数据范围】
对于 $100\%$ 的数据，$6\le n\le 13$。

解题思路

• 1）根据题目要求， 每行只能放一个皇后，每列只能放一个皇后，每一个“/”斜行只能放一个皇后，每一个“\”斜行只能放一个皇后，我们用数组check来保证每列和每条对角线上只有一个棋子。check[0]储存了棋子的列数，每一次进行 ans[line]=i，使 check[0][i] 标记为已使用。同理check[1]和check[2]储存对角线上的棋子分布情况。
• 2）若满足条件，if((!used[0][i])&&(!used[1][line+i])&&(!used[2][line-i+n]))，即可在此处下棋，将check数组中的相应数值标记为已使用，并对下一行进行深度优先搜索。
• 3）输出前三组解。

参考代码

#include
using namespace std;
int ans[14],used[3][28]={0},sum=0,n;

int check(int i,int line)
{
    if((!used[0][i])&&(!used[1][line+i])&&(!used[2][line-i+n]))
        return 1;
    return 0;
}

void dfs(int line)
{
    if(line>n)
    {
        sum++;
        if(sum>3) return;
        else
        {
            for(int i=1;i<=n;i++) printf("%d ",ans[i]);
            printf("\n");
            return;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(check(i,line))
        {
            ans[line]=i;
            used[0][i]=1; used[1][line+i]=1; used[2][line-i+n]=1;
            dfs(line+1);
            used[0][i]=0; used[1][line+i]=0; used[2][line-i+n]=0;
        }
    }
}
int main()
{
    scanf("%d",&n);
    dfs(1);
    printf("%d",sum);
    return 0;
}
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

[NOIP2005 普及组] 采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 $2$ 个整数 $T$（$1\le T\le 1000$）和 $M$（$1\le M\le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例 #1

样例输入 #1

70 3
71 100
69 1
1 2
1
2
3
4

样例输出 #1

3
1

提示

【数据范围】

• 对于 $30\%$ 的数据，$M\le 10$；
• 对于全部的数据，$M\le 100$。

解题思路

• 1）简单的01背包问题，直接套板子

参考代码

#include
using namespace std;
int dp[1050];
int main()
{
	int T,M;
	cin>>T>>M;
	for(int i=1;i<=M;i++)
	{
		int t,v;
		cin>>t>>v;
		for(int j=T;j>=t;j--)
		{
			dp[j]=max(dp[j],dp[j-t]+v);
		}
	}
	cout<

300 4
100 60
250 120
120 100
35 20
1
2
3
4
5

605
1

#include
using namespace std;
long long dp[10200];
int main()
{
	int m,n;
	cin>>m>>n;
	
	for(int i=1;i<=n;i++)
	{
		int p,t;
		cin>>p>>t;
		for(int j=t;j<=m;j++)
		{
			dp[j]=max(dp[j],dp[j-t]+p);
		}
	}
	cout<