首页 > 搜索 > DFS搜索 > HDU 1655 Pascal Program Lengths-动态规划-[解题报告] C++
2013
12-21

HDU 1655 Pascal Program Lengths-动态规划-[解题报告] C++

Pascal Program Lengths

问题描述 :

Your local computer user’s group publishes a quarterly newsletter, and in each issue there is a small Turbo Pascal programming problem to be solved by the membership. Members submit their solutions to the problem to the newsletter editor, and the member submitting the shortest solution to the problem receives a prize.

The length of a program is measured in units. The unit count is determined by counting all occurrences of reserved words, identifiers, constants, left parentheses, left brackets, and the following operators: +, -, *, /, =, <, >, <=, >=, <>, @, ^, and :=. Comments are ignored, as are all other symbols not falling into one of the categories mentioned above. The program with the lowest unit count is declared the winner. Two or more programs with equal unit counts split the prize for the quarter.

In an effort to speed the judging of the contest, your team has been asked to write a program that will determine the length of a series of Pascal programs and print the number of units in each.

输入:

Input to your program will be a series of Turbo Pascal programs. Each program will be terminated by a line containing tilde characters in the first two columns, followed by the name of the submitting member. Each of these programs will be syntactically correct and use the standard symbols for comments (braces) and subscripts (square brackets).

输出:

For each program, you are print a separate line containing the name of the submitting member and the unit count of the program. Use a format identical to that of the sample below.

样例输入:

PROGRAM SAMPLEINPUT;

VAR
  TEMP : RECORD
    FIRST, SECOND : REAL;
    END;

BEGIN {Ignore this }
TEMP.FIRST := 5.0E-2;
READLN (TEMP.SECOND); 
WRITELN ('THE ANSWER IS', TEMP.FIRST * TEMP.SECOND : 7 : 3)
END.
~~A. N. Onymous

样例输出:

Program by A. N. Onymous contains 29 units.


Note: Here are some additional notes on Turbo Pascal for those not familiar with the language: 

Identifiers start with an underscore (_) or a letter (upper or lower case) which is followed by zero or more characters that are underscores, letters or digits.
The delimiter for the beginning and ending of a string constant is the single forward quote ('). Each string is entirely on a single source line (that is a string constant cannot begin on one line and continue on the next). If '' appears within a string then it represents a single ' character that is part of the string. A string constant consisting of a single ' character is, therefore, represented by '''' in a Turbo Pascal program. The empty string is allowed.
The most general form of a numeric constant is illustrated by the constant 10.56E-15. The 10 is the integral part (1 or more digits) and is always present. The .56 is the decimal part and is optional. The E-15 is the exponent and it is also optional. It begins with an upper or lower case E, which is followed by a sign (+ or -). The sign is optional.
Turbo Pascal supports hexadecimal integer constants which consist of a $ followed by one or more hex digits (`0' to `9', `a' to `f', `A' to `F'). For example, $a9F is a legal integer constant in Turbo Pascal.
The only comment delimiters that you should recognise are {}, and not (**). Comments do not nest.
`+' and `-' should be considered as operators wherever possible. For example in 
x := -3 the `-' and the `3' are separate tokens.
Subranges of ordinal types can be expressed as lower..upper. For example, 1..10 is a subrange involving the integers from 1 to 10.
All tokens not mentioned anywhere above consist of a single character. 

也是个简单树状DP,和POJ3107的写法基本一致。

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;
#define ll long long
#define int64 __int64
#define M 100005
#define N 1005
#define inf 1000010
#define mod 1000000007

struct node
{
	int son_max;
	int son_sum;
	int pos;
}tp[M];
struct Node
{
	int ev , next;
}tree[M];
int n , tot , head[M];

void Add(int s , int e)
{
	tree[tot].ev = e;
	tree[tot].next = head[s];
	head[s] = tot++;
}

void Dfs(int s , int fa)
{
	int i;
	tp[s].son_max = 0;
	tp[s].son_sum = 1;
	tp[s].pos = s;
	for (i = head[s] ; i != -1 ; i = tree[i].next)
	{
		int v = tree[i].ev;
		if (v == fa)continue;
		Dfs(v,s);
		tp[s].son_max = max(tp[s].son_max , tp[v].son_sum);
		tp[s].son_sum += tp[v].son_sum;
	}
	tp[s].son_max = max(tp[s].son_max , n-tp[s].son_sum);
}

bool cmp(node a , node b)
{
	if (a.son_max < b.son_max)return true;
	if (a.son_max > b.son_max)return false;
	if (a.pos < b.pos)return true;
	return false;
}

int main()
{
	int i , t;
	scanf("%d",&t);
	while (t--)
	{
		tot = 0;
		memset(head , -1 , sizeof head);
		scanf("%d",&n);
		for (i = 1 ; i < n ; i++)
		{
			int s , e;
			scanf ("%d%d",&s,&e);
			Add(s,e);
			Add(e,s);
		}
		Dfs(1,0);
		sort(tp+1 , tp+n+1 , cmp);
		printf("%d %d\n",tp[1].pos,tp[1].son_max);
	}
	return 0;
}

 

解题报告转自:http://blog.csdn.net/wangjie_wang/article/details/9257109


  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }