首页 > ACM题库 > HDU-杭电 > HDU 2963-When-动态规划-[解题报告]HOJ
2014
02-24

HDU 2963-When-动态规划-[解题报告]HOJ

When

问题描述 :

"When" is an event driven language for machine control. It only has three statements: Set, Print, and the compound When clause. The (case insensitive) grammar is as follows

PROGRAM := WHEN | PROGRAM WHEN
WHEN := ‘when ‘ EXPRESSION EOL STATEMENTS ‘end when’ EOL
STATEMENTS := STATEMENT | STATEMENTS STATEMENT
STATEMENT := PRINT | SET
PRINT := ‘print ‘ EXPRESSION_LIST EOL
SET := ‘set ‘ ASSIGNMENT_LIST EOL
EXPRESSION_LIST := EXPRESSION | EXPRESSION_LIST ‘,’ EXPRESSION
ASSIGNMENT_LIST := ASSIGNMENT | ASSIGNMENT_LIST ‘,’ ASSIGNMENT
ASSIGNMENT := VARIABLE ‘=’ EXPRESSION
EXPRESSION := ‘(‘ EXPRESSION OP EXPRESSION ‘)’ | VARIABLE | NUMBER
OP := ‘<’ | ‘+’ | ‘-’ | ‘and’ | ‘or’ | ‘xor’
VARIABLE := ‘$’ NOT_DOLLAR_STRING ‘$’
NUMBER := DIGIT | NUMBER DIGIT
DIGIT := ’0′ | .. | ’9′
NOT_DOLLAR_STRING := any sequence of printing characters (including blanks)
that does not contain a $ symbol.

In the above, any string enclosed in single quotes are to be treated literally. EOL is the end of line.

In words, a program consists of a list of when blocks, which themselves contain set and print statements. Case is ignored for key words and variable names. Spaces are allowed before or after any literal except inside a number. Spaces are allowed in variable names, and each non-empty sequence of spaces is treated as a single underscore, so the following refer to the same variable

$Remote Switch#1$
$Remote_Switch#1$
$Remote switch#1$

All variable and literal values are integers between -1000000000 and 1000000000, inclusively. All variables are global and initially zero. The when programs you will be tested on will never have an EXPRESSION that evaluates to a value outside of this range. The logical operators evaluate to 0 for false and 1 for true, and treat any nonzero value as true.

Running the When program amounts to executing all the active when clauses until none are active. More specifically, the active list of when clauses is initially empty, then the following steps are repeated:

* In the order they appear in the program, the conditions of all when clauses that are not currently active are evaluated. If true, the clause is added to the end of the active list, with its first statement marked as "ready". Each active when clause has one "ready" statement.
* If the active list is empty after this step, the program terminates.
* The "ready" statement from the "current" when clause (initially the first clause in the active list) is executed.
* The statement marked as "ready" is advanced, removing the when clause from the active list if this is the last statement in the "current" when clause.
* The when clause marked as "current" is advanced, cycling to the beginning of the active list if the end is reached.

In other words, inactive when conditions are evaluated to determine if these clauses are added to the active list. Then one statement (set or print) is executed from the current active when clause. If this is the last statement in that clause, it is removed from the active list. One the next iteration, one statement is executed from the next active when clause, etc.

A set statement executes all the assignments concurrently, so that

set $x$=$y$,$y$=$x$

swaps the values of $x$ and $y$. The same variable cannot appear twice on the left hand part of the same set statement (so set $x$=1,$x$=2 is illegal).

A print statement evaluates and prints the given expressions in the output, separated by commas and followed by a new line. So

  print 1,(2+3)

results in the line

  1,5

in the output.

输入:

The input consists of several test cases separated by a blank line. Each of them is a single syntactically correct program. You may assume that the program will not execute more than 100000 set statements and 100000 print statements.

输出:

The input consists of several test cases separated by a blank line. Each of them is a single syntactically correct program. You may assume that the program will not execute more than 100000 set statements and 100000 print statements.

样例输入:

When ($Mr. Bill$<5)
   Set $mr._bill$=($mr.  bill$+1),$Y$=($Y$+10)
End When
When ($mr. Bill$<10)
  Set $MR. BILL$=($mr. bill$+1)
  Print $mr. bill$,$Y$
End When

样例输出:

3,20
6,40
7,40
8,40
9,40
10,40

1.题目

http://acm.hdu.edu.cn/showproblem.php?pid=2639

2.分析

01背包的变种第k大01背包解决方法是从01背包的解法中改进而来。每次转移状态时,选择当前容量下的前k个价值,再找前面状态转移过来的前k个价值,然后合并,找出不相等的前k个价值,如果不多于k的话则用0补上,这样在总价值种数不足k的时候也可直接输出0.这样不断转移都可以保证找到前k大的价值(找不到也会是0)。本题复杂度为(O(NVK)),开始的时候我用了优先队列存放前k大的价值,很容易想,但速度不够快,后来改成合并两个有序序列的方法,时间从1564ms->109ms。(引用文献1)

3.复杂度

虽然和普通01背包不同,但是由于附加值是常数,因此时间和空间复杂度不变;

时间复杂度O(VNK);空间复杂度O(VK);

4.涉及内容

动态规划

5.感想

把《背包九讲》上的经典题目好好做做。对于其他方面DP、数据结构等也是如此、

6.代码

#include <iostream>
using namespace std;
#define max(a,b) (a>b?a:b)
long f[1001][31];
long pre[31],cur[31];
int T,N,V,K,v[1000];
void ZeroOnePack(int cost,int weight)
{
	for(int i=V;i>=weight;--i)//典型01背包,倒序处理
	{
		int j;
		for(j=1;j<=K;++j)
		{
			pre[j]=f[i-weight][j]+cost;//从大到小排序,方便最后合并找最大的前K个值
			cur[j]=f[i][j];//从大到小排序,方便最后合并找最大的前K个值
		}
		pre[j]=cur[j]=-1;
		int fi=1,pi=1,ci=1;
		while(fi<=K && (pre[pi]!=-1 || cur[ci]!=-1))
		{
			if(pre[pi]>cur[ci]) f[i][fi]=pre[pi++];
			else f[i][fi]=cur[ci++];
			if(f[i][fi]!=f[i][fi-1]) ++fi;
		}
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	int tempcost=0;
	long maxdata=0;
	cin>>T;
	while(T--)
	{
		memset(f,0,sizeof(f));
		memset(v,0,sizeof(v));
		memset(pre,0,sizeof(pre));
		memset(cur,0,sizeof(cur));
		cin>>N>>V>>K;
		for(int i=0;i<N;++i)
			cin>>v[i];
		for(int i=0;i<N;++i)
		{
			cin>>tempcost;
			ZeroOnePack(v[i],tempcost);
		}
		cout<<f[V][K]<<endl;
	}
	return 0;
}

7.参考文献

1.http://blog.csdn.net/woshi250hua/article/details/7613901 (通过归并找前K个最大值;通过优先队列找前K个最大值;两种思路)

解题参考:http://blog.csdn.net/qiusuo800/article/details/12217859


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢