文章列表
这是一个很典型的动态规划中的01背包问题，G个砝码，每个砝码有C种放法。我们就可以按砝码的个数划分状态，共有G种状态，每种状态有多个选择，每次加一个砝码为一次状态转移，状态转移方程为:
for(i=1;i<gNum;i++){
for(j=0;j<=15000;j++){
for(k=0;k<cNum;k++){
value = j-C[k]*G[i];
if((value>=0)&&(value<=15000)){
...
poj3295解题报告
- 博客分类：
- poj解题报告
挺简单的一道题目，练练手。思路很简单，和计算器比较像，将表达式带入值通过栈进行运算，一个循环是32次，列举pqrst所有的值的情况，如果32种情况得到的值相同则为正确的。
值得一提的是采用多个数组简化运算，de保存了运算符"KANCE"的运算规则，se保存了32种情况下"pqrst"的值情况，通过这两个数组使得运算简化
Problem: 3295 User: godfrey90
Memory: 388K Time: 0MS
Language: G++ Result: Accepted
Source Code
#include <cs ...
一道很简单的模拟题
#include<cstdio>
int main() {
int a, b, X, vx, vy, vz;
scanf("%d%d%d%d%d%d", &a, &b, &X, &vx, &vy, &vz);
if (vx <= 0)
printf("impossible\n");
else {
double fx = X;
double t = fx / vx;
double sy = vy * t;
double s ...
这道题目的解题思路是动态规划，通过N和K进行状态转移
#include <cstdio>
#include <cmath>
int a[40][900];
int n,k;
void work(){
a[1][1]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<=(i+1)*i/2;j++){
a[i][j]=0;
if((i+j)<=(i-1)*i/2){
a[i][j]+=a[i-1][i+j];
}
if(j!=0){
if(i>= ...
本题思路，首先求出每两点之间的距离，储存在d中，然后穷举所有情况，通过海伦公式计算三角形面积，找出最大的面积。
#include<cstdio>
#include<cmath>
int n;
int x[110];
int y[110];
double d[110][110];
double result=0;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&x[i],&y[i]);
...
这是一道稍微有点难度的模拟题，通过模拟实际运行的情况，通过队列进行宽搜，重点在于判断齿轮会不会卡住，最后得出结论。
1.算法
(1)预处理：
将所有的齿轮坐标和半径读取，保存在x,y,r三个数组中，然后进行相切判断，两两进行判断，将结果放置在map中，map[i][0]表示有几个齿轮和第i个齿轮相切，map[i][1～x]分别表示和第i个齿轮相切的x个齿轮的号码。
(2)操作：
依次对1～n中的每一个齿轮做检查，判断如果将该齿轮去掉能不能成功。检查操作如下：
从1号齿轮开始，根据map中的相切情况，依次向后进行宽搜，直到搜索到最后一个目标齿轮。
在这个过程中需要注意的是判断齿轮是否会卡住，这里采 ...
#include<cstdio>
#include<cstring>
int main(){
int m,n;
int result=0;
char str[1000][10];
scanf("%d%d",&m,&n);
for(int i=0;i<m;i++){
scanf("%s",str[i]);
}
char str_temp[10];
for(int i=0;i<n;i++){
scanf("%s",str_temp); ...
#include<cstdio>
double mul(double x,int y){
double result=1.0;
for(int i=0;i<y;i++){
result*=x;
}
return result;
}
int main(){
int n=0;
double A=0,B=0;
double a[11];
double res_A;
double res_B;
scanf("%d%lf%lf",&n,&A,&B);
for(int i=0;i< ...
#include<cstdio>
int main(){
int m,n;
double min[100];
double temp;
double result;
scanf("%d %d",&m,&n);
for(int j=0;j<m;j++){
scanf("%lf",&temp);
min[j]=temp;
}
for(int i=1;i<n;i++){
for(int j=0;j<m;j++){
scanf("%l ...
D. 穿越机房
问题描述
众所周知,在机房里想从一个地方到另一个地方很困难。因为机房里不仅有很多的
桌子,还摆了很多的椅子。现在,建冬哥想找嘉娃一起 apom,他不能在众目睽睽之下
对着嘉娃大吼,所以,他必须走到嘉娃跟前。
我们把机房分为宽度为 w,高度为 h 的 w × h 个格子。每个格子或者是一张桌子,
或者有一把椅子,或者什么都没有。建冬哥不能通过有桌子的格子,可以以一个单位时
间通过什么都没有的格子,但是通过有椅子的格子时,建冬哥需要花两个单位时间。
现在给出建冬哥和嘉娃的位置,以及机房的构造,你能知道建冬哥最快要多 ...
C. 大作业
问题描述
由于之前宅得太深,到了期末了,嘉娃还有 N 个大作业没有写。以嘉娃的速度,他
每天能且只能完成一个大作业。但是这 N 门大作业都有一个截止时间,如果超过这个
时间再提交的话将会没有分数。现在,嘉娃要在 N 天内完成 N 门大作业,他给了你一
份有 N 个大作业的截止时间和分数的列表,你能帮嘉娃算出他最多能得到多少分吗?
输入格式
第一行一个整数 N (0 ≤ N ≤ 1000),表示大作业的数目。接下来 N 行,每行两个
整数。 di (1 ≤ di ≤ N ) 表示第 i 个大作业的截止时间,以嘉 ...
B. 嘉娃的难题
问题描述
嘉娃的家庭作业里有很多数列填空练习题。填空练习题的要求是:已知数列的前四
项,填出第五项。因为已经知道这些数列只可能是等差或者等比数列,所以他决定写一
个程序来完成这些练习。
输入格式
第一行是数列的数目 T (0 ≤ T ≤ 40)。接下来 T 行每行均包含四个整数,表示一个
数列的前四项。数列的前五项均为绝对值不大于 109 的自然数,等比数列的比值也是自
然数。
输出格式
对输入的每个数列,输出它的前五项,每一行的末尾没有多余空格。
样例输入
2
-1 -2 -3 -4
1 2 4 8
样例输出
-1 -2 -3 -4 ...
A. 采购
问题描述
作为资深宅男,嘉娃醒着的时候就坐在电脑前。为了提高宅的效率,他连下楼吃饭
的时间都不放过了。于是他需要每隔一段时间去超市进行一次大采购来保证有充足的
食物储备。
嘉娃的学校里有两家超市,嘉娃每次只能去一家超市采购。为了省钱买点卡,嘉娃
搞到了一份两家超市的物价表。不过嘉娃不想在算帐上浪费时间,现在他给了你一份
他的购物清单,你能帮助嘉娃算出去哪家超市购物便宜吗?
输入格式
第一行一个整数 N (0 ≤ N ≤ 1000),表示嘉娃要买多少种物品。
下面共 2N 行。第 2i 行包含 ...
1.算法
本题是一道贪心题，和《算法艺术与信息学竞赛》中的“照亮的山景”题极为相似。
(1)首先我们求出在每个岛屿放雷达以后在x轴上所能覆盖的区间，是在x轴的上的一个线段，即在这一段上放置雷达可以覆盖到该岛。
(2)我们把每个岛对应的线段找出来，只要在这些线段上放置一些雷达，使得所有的线段上都有雷达即可符合题意（注意如果半径为0或者坐标的y轴小于半径的话将无法完成覆盖，输出-1）。
(3)我们将线段根据左端点排序，找出如果一个线段包含另一个线段，则可以忽略外面的那一个线段（道理很简单），将其设为无效。
(4)在剩下的线段中从左往右遍历，对于每个线段，尽量选取该线段的最右边的点作为雷达，如果之前有 ...