去去。

不会的题就写暴力。

[USACO07JAN]解决问题Problem Solving

题目描述

In easier times, Farmer John’s cows had no problems. These days, though, they have problems, lots of problems; they have P (1 ≤ P ≤ 300) problems, to be exact. They have quit providing milk and have taken regular jobs like all other good citizens. In fact, on a normal month they make M (1 ≤ M ≤ 1000) money.

Their problems, however, are so complex they must hire consultants to solve them. Consultants are not free, but they are competent: consultants can solve any problem in a single month. Each consultant demands two payments: one in advance (1 ≤ payment ≤ M) to be paid at the start of the month problem-solving is commenced and one more payment at the start of the month after the problem is solved (1 ≤ payment ≤ M). Thus, each month the cows can spend the money earned during the previous month to pay for consultants. Cows are spendthrifts: they can never save any money from month-to-month; money not used is wasted on cow candy.

Since the problems to be solved depend on each other, they must be solved mostly in order. For example, problem 3 must be solved before problem 4 or during the same month as problem 4.

Determine the number of months it takes to solve all of the cows’ problems and pay for the solutions.

P个问题，雇佣相同的人去解决，每个人每月解决一道题，每个人解决问题的代价都分两次，解决问题当月给a[i],事后第二月给b[i],然后每个月有m的钱，问最快多久解决所有问题。（问题必须按照序号一个个解决）这个月用上个月的钱支付，然后结余会用来买糖

输入输出格式

输入格式：

Line 1: Two space-separated integers: M and P.

Lines 2..P+1: Line i+1 describes problem i with two space-separated integers: Bi and Ai. Bi is the payment to the consult BEFORE the problem is solved; Ai is the payment to the consult AFTER the problem is solved.

输出格式：

Line 1: The number of months it takes to solve and pay for all the cows’ problems.

输入输出样例

输入样例#1：

输出样例#1：

题解

暴力只需要读懂题意。

我们枚举每个问题的月份，然后开一个数组维护每个月用了多少钱，需要满足题目限制。

注意要求递增，所以这个东西实现一下跑的很快，但是会WA，有30，挺好。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 1005
int f[maxn][maxn] , g[maxn][maxn] , M , n , c[maxn] , t[maxn] , ans , flag , a[maxn] , b[maxn];
void dfs(int x , int la)
{
	if(flag) return;
	if(x == n + 1){
		ans = c[la + 1] ? la + 1 : la;
		flag = true;
		return;
	}
	for(int i = la ; i <= 2 * n ; ++i)
	{
		if(c[i] + a[x] <= M && c[i + 1] + b[x] <= M)
		{
			c[i] += a[x];
			c[i + 1] += b[x];
			t[x] = i;
			dfs(x + 1 , i);
			if(flag) return;
			c[i] -= a[x];
			c[i + 1] -= b[x];
			t[x] = 0;
		}
	}
}

int main()
{
	scanf("%d%d",&M,&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d%d",&a[i],&b[i]);
	dfs(1 ,1);
	printf("%d\n",ans + 1);
}

正解大概是个dp。

鉴于今天写暴力，略去。

[USACO07FEB]牛的词汇The Cow Lexicon

题目描述

Few know that the cows have their own dictionary with W (1 ≤ W ≤ 600) words, each containing no more 25 of the characters ‘a’..’z’. Their cowmunication system, based on mooing, is not very accurate; sometimes they hear words that do not make any sense. For instance, Bessie once received a message that said “browndcodw”. As it turns out, the intended message was “browncow” and the two letter “d”s were noise from other parts of the barnyard.

The cows want you to help them decipher a received message (also containing only characters in the range ‘a’..’z’) of length L (2 ≤ L ≤ 300) characters that is a bit garbled. In particular, they know that the message has some extra letters, and they want you to determine the smallest number of letters that must be removed to make the message a sequence of words from the dictionary.

没有几个人知道,奶牛有她们自己的字典,里面的有W (1 ≤ W ≤ 600)个词,每个词的长度不超过25,且由小写字母组成.她们在交流时,由于各种原因,用词总是不那么准确.比如,贝茜听到有人对她说”browndcodw”,确切的意思是”browncow”,多出了两个”d”,这两个”d”大概是身边的噪音.

奶牛们发觉辨认那些奇怪的信息很费劲,所以她们就想让你帮忙辨认一条收到的消息,即一个只包含小写字母且长度为L (2 ≤ L ≤ 300)的字符串.有些时候,这个字符串里会有多余的字母,你的任务就是找出最少去掉几个字母就可以使这个字符串变成准确的”牛语”(即奶牛字典中某些词的一个排列).

输入输出格式

输入格式：

Line 1: Two space-separated integers, respectively: W and L

Line 2: L characters (followed by a newline, of course): the received message

Lines 3..W+2: The cows’ dictionary, one word per line

• 第1行:两个用空格隔开的整数,W和L.

• 第2行:一个长度为L的字符串,表示收到的信息.

• 第3行至第W+2行:奶牛的字典,每行一个词.

输出格式：

Line 1: a single integer that is the smallest number of characters that need to be removed to make the message a sequence of dictionary words.

一个整数,表示最少去掉几个字母就可以使之变成准确的”牛语”.

输入输出样例

输入样例#1：

6 10
browndcodw
cow
milk
white
black
brown
farmer

输出样例#1：

题解

幸好这次题意十分清楚。

暴力做法可以这样。

枚举字符串子集，枚举字典序子集排列，然后算hash进行比较。

由于比较闲，可以算一下复杂度：
$\sum{i=1}^{n}\binom{n}{i}\sum{j=1}^{w}\binom{w}{j}j!*i\sum len_j$

(算复杂度已经没有意义了。)

可以加一个很有用的优化，预处理所有字典单词子集的长度，只有当母串子集与字典子集长度相同时再比较。

这样期望复杂度会变小很多。

~~代码来不及写了不写了~~

Typora换成solarized真舒服。