[Topcoder SRM 499]【Solution】

55555,当时在学校没法捉……

250

有n只兔子,其中k(k<=n)只说了话,说话的形式如:和我一样颜色的有A[i]只!

然后问,满足这些话的情况下,n最小能是多少。

就是A[i]一样的贪心组合在一起即可。

550

给定一个数组A[i](i=0~n-1),假设你操作的序列是B[i](i=0~m-1)。

初始时m=1,B[0]=0

然后有3种操作:

1、将某个B[i] +1

2、将某个B[i] -1

3、选一个i然后

for (int j=m;j>i;j–) B[j]=B[j-1];

m++;

然后问最少进行多少操作,B[i]能和A[i]一样。

只要注意到复制以后,i和后面就可以断绝联系,这个区间dp的形式还是很明显的,F[i,j,k]表示区间[i,j]由一个初始时B[i]=k的复制而成至少需要多少次操作,然后枚举复制的位置和复制的长度就可以转移了。O(n^5) TC服务器无压力T_T

还有一种神贪心:

int getMinimum(vector

int ret=lines[0]+lines.size()-1;

for (int i=1;i

 if (lines[i]>lines[i-1]) ret+=lines[i]-lines[i-1];

return ret;

}

暂时只证明了他的充分性,必要性不会证T_T

 

1000

这个我觉得是我见过最简单的1000了啊啊啊T_T。

注意它可以交换相邻两个,那么你想想冒泡排序吧,于是所有的顺序都可以排出来了。所以用数量就可以描述一个点。

Tarjan缩环(注意缩完以后已经是拓扑序的了),然后dp求最长路就行了。每个点权就是k!/(pA! * pB! *pC! *pD!) pA表示’A’的数量……

 

加入对话

2条评论

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注