USACO Numbering the Cows(cownum)

Problem cownum: Numbering the Cows [Romanian Olympiad, 2001]

Farmer John wants to assign a (not necessarily distinct) integer

in the range 1..N (3 <= N <= 1,000) to each of his N cows for

identification purposes. Thus, he lined up all his cows in order

and came up with the following rule: the i-th cow in line must be

assigned an integer that is less than the integers assigned to cows

i+2 and i+3.

FJ wants to know the total number of possible assignments he might

make. If cow i+2 does not exist, then cow i does not have the

constraint that its ID number must be less than that of cow i+2.

Likewise if cow i+3 does not exist.

Since Farmer John is not too good at math and might be confused by

large numbers, output the answer modulo M (1 <= M <= 10,000,000).

PROBLEM NAME: cownum

INPUT FORMAT:

Two space-separated integers: N and M.

SAMPLE INPUT (file cownum.in):

3 10000

OUTPUT FORMAT:

A single line containing the number of assignments modulo M.

SAMPLE OUTPUT (file cownum.out):

9

OUTPUT DETAILS:

There are 9 valid assignments: (1,1,2), (1,1,3), (1,2,2), (1,2,3), (1,3,2),

(1,3,3), (2,1,3), (2,2,3), (2,3,3).

先orz一下xt神牛（虽然我不认识）的神奇DP

设f[i,j]表示前i头牛编号不大于j的方案数

若a[i]<>j，则总数累加f[i,j-1]，否则(a[i]=j时)，分以下情况累加

i)a[i-2]=a[i-1]时，总数为f[i-2,j-1]

ii)a[i-2]>a[i-1]时，总数为f[i-1,j-1]

iii)a[i-2]<a[i-1]时，总数为f[i-2,j-1]+f[i-2,j-2]+f[i-2,j-3]+…+f[i-2,1]（这一处似乎和神牛的题解有些出入，他是从f[i-2,j-2]开始累加的）

边界f[1,k]=k   f[2,k]=n*n

不过现在是O(n^3),所以需要优化:g[i,j]=f[i,1]+f[i,2]+…+f[i,j]

接下来程序验证……（待续）

xt真神牛也，他的方程是对的，我的是错的。这是为什么呢？回去继续研究。

{2009年7月22日0:33:50

看过USACO题解后，终于明白哪里错了

这一句“若a[i]<>j，则总数累加f[i,j-1]”就开始错，因为a[i-1]可能为j

下面重新定义f[i,j]的计算方式：

1、用1~j-1编号这i头牛（f[i,j-1]）

2、最后两头牛都为j（f[i-2,j-1]）

3、最后一头为j，其他前面的小于j（f[i-1,j-1]）

4、倒数第二头为j，最后一头小于j（f[i-2,j-2]+f[i-2,j-2]+f[i-2,j-3]+…+f[i-2,1]）

这下就对了

2009年7月22日0:41:08}

下贴上几个月以来第一段程序代码，一年以来第一个C++代码，以及n久以来第一次切题通过记录：

/*
PROG: cownum
LANG: C++
ID: tjbwyk1
*/

#include<fstream>
using namespace std;
ifstream input("cownum.in");
ofstream output("cownum.out");

const int maxn=1002;
int f[maxn][maxn],g[maxn][maxn],n,m,i,j;

void init()
{
input>>n>>m;
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
for (i=1; i<=n; i++)
{
f[1][i]=i%m;
f[2][i]=i*i%m;
g[1][i]=(g[1][i-1]+f[1][i])%m;
g[2][i]=(g[2][i-1]+f[2][i])%m;
}
}

void doit()
{
for (i=3; i<=n; i++)
for (j=1; j<=n; j++)
{
f[i][j]=(f[i][j-1]+f[i-2][j-1]+f[i-1][j-1]+g[i-2][j-2])%m;
g[i][j]=(g[i][j-1]+f[i][j])%m;
}
}

void outit()
{
output<<f[n][n]<<endl;
}

int main()
{
init();
doit();
outit();
input.close();
output.close();
return 0;
}

华丽的记录：

USER: Yikang Wang [tjbwyk1]

TASK: cownum

LANG: C++

Compiling…

Compile: OK

Executing…

Test 1: TEST OK [0.022 secs]

Test 2: TEST OK [0.022 secs]

Test 3: TEST OK [0.032 secs]

Test 4: TEST OK [0.022 secs]

Test 5: TEST OK [0.011 secs]

Test 6: TEST OK [0.022 secs]

Test 7: TEST OK [0.022 secs]

Test 8: TEST OK [0.022 secs]

Test 9: TEST OK [0.022 secs]

Test 10: TEST OK [0.054 secs]

Test 11: TEST OK [0.043 secs]

Test 12: TEST OK [0.054 secs]

Test 13: TEST OK [0.043 secs]

Test 14: TEST OK [0.054 secs]

Test 15: TEST OK [0.054 secs]

Test 16: TEST OK [0.065 secs]

All tests OK.

YOUR PROGRAM (‘cownum’) WORKED FIRST TIME! That’s fantastic

— and a rare thing.  Please accept these special automated

congratulations.

Test Data | Analysis

Keep up the good work!

下一个任务由烧白同学指派，Turning in Homework