while(scanf("%d",&n)!=EOF){
for(int i=0;i<10;i++)
scanf("%d",&a[i]);
for(int i=0;i<=n;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j
}
memset(dp,0,sizeof(dp));
dp[10][0]=1;
for(int i=9;i>=0;i--){
for(int j=n;j>=0;j--)
for(int k=j-a[i];k>=0;k--)
if(i) dp[i][j]=(dp[i][j]+dp[i+1][k]*c[j][k])%MOD;
else if(j&&k) dp[i][j]=(dp[i][j]+dp[i+1][k]*c[j-1][k-1])%MOD;
}
LL ans=0;
for(int i=0;i<=n;i++)
ans=(ans+dp[0][i])%MOD;
printf("%I64d\n",ans);
}
return 0;
}
E. Relay Race
NOIP 2008 传纸条，单向很简单，双向的可以考虑成两个人同时从（1，1）到（n，n）。那么用四维的表示两个人的位置就行了，但是这题N达到300，四维的不行。
由于两个人同时在移动，所以x1+y1=x2+y2。那么可以省去一维，我们还可以用dp[i][j][k]表示走了i步，两个人分别是第j行，第k行，则第一个人在i-j+2列，第二个人在i-k+2列。
转移的时候注意不要交叉，而且到达同一位置的时候不能多取。
可能为负，注意初始化
[cpp]
#include
#include
#include
#include
#include
#define N 305
#define inf 1<<29
#define MOD 9973
#define Max 301
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)
using namespace std;
int dp[N<<1][N][N];
int a[N][N],n;
int way[4][2]={{0,0},{0,1},{1,0},{1,1}};
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
memset(dp,0x81,sizeof(dp));
dp[0][1][1]=a[1][1];
for(int i=1;i<=2*n-2;i++)
for(int j=1;j<=i+1&&j<=n;j++)
for(int k=j;k<=i+1&&k<=n;k++){
for(int r=0;r<4;r++)
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-way[r][0]][k-way[r][1]]);
dp[i][j][k]+=a[j][i-j+2]+a[k][i-k+2]-(j==k a[k][i-k+2]:0);
}
printf("%d\n",dp[2*n-2][n][n]);
}
return 0;
作者：ACM_cxlove