【NOIP2009PJ】道路游戏

啊哈，现在有重温了一遍o(╥﹏╥)o
从以前的O(n²)——>现在的O（n³），感觉自己废了~
（尽管代码大幅度减少）
我们可以发现p其实只是一个限制的作用，不需要枚举啊，它是一个个走的，所以只需要记录一下就行了┭┮﹏┭┮

uses math;
var
        f,g:array[0..1001,0..1001,0..1] of longint;
        a:array[1..1001,1..1001] of longint;
        b:array[1..1001] of longint;
        n,m,p,i,j,k,max1,max2:longint;
begin
        assign(input,'game.in');reset(input);
        assign(output,'game.out');rewrite(output);
        readln(n,m,p);
        for i:=1 to n do
                for j:=1 to m do
                        read(a[i,j]);
        for i:=1 to n do
                read(b[i]);
        for i:=1 to m do
        begin
                for j:=1 to n do
                begin
                        k:=j-1;
                        if k=0 then k:=n;
                        if (g[i-1,k,1]>0) and (g[i-1,k,0]>0) and (g[i-1,k,1]+1<=p) and (g[i-1,k,0]+1<=p) then
                        begin
                                if f[i-1,k,1]>f[i-1,k,0] then
                                begin
                                        f[i,j,0]:=f[i-1,k,1]+a[j,i];
                                        g[i,j,0]:=g[i-1,k,1]+1;
                                end else
                                begin
                                        f[i,j,0]:=f[i-1,k,0]+a[j,i];
                                        g[i,j,0]:=g[i-1,k,0]+1;
                                end;
                        end else if (g[i-1,k,1]>0) and (g[i-1,k,1]+1<=p) then
                        begin
                                f[i,j,0]:=f[i-1,k,1]+a[j,i];
                                g[i,j,0]:=g[i-1,k,1]+1;
                        end else if (g[i-1,k,0]>0) and (g[i-1,k,0]+1<=p) then
                        begin
                                f[i,j,0]:=f[i-1,k,0]+a[j,i];
                                g[i,j,0]:=g[i-1,k,0]+1;
                        end;
                        f[i,j,1]:=a[j,i]-b[j]+max1;
                        g[i,j,1]:=1;
                        max2:=max(max(f[i,j,1],f[i,j,0]),max2);
                end;
                max1:=max2;
        end;
        writeln(max1);
        close(input);
        close(output);
end.

只看我傻傻地打了个n三方

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,p,f[2][1010][1010],g[1010][1010],c[1010],ans=0;

inline int read()
{
	int x=0; char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}

int main()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	n=read(),m=read(),p=read();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++) g[i][j]=read();
	for (int i=1;i<=n;i++) c[i]=read();
	memset(f,128,sizeof(f));
	for (int i=1;i<=n;i++) f[0][i][0]=-c[i];
	for (int i=1,mx,x=1,las=0;i<=m;i++,las=x,x^=1)
	{
		mx=0;
		for (int j=1,la;j<=n;j++)
		{
			la=(j+n-2)%n+1;
			for (int k=1;k<=min(i,p);k++)
			{
				f[x][j][k]=f[las][la][k-1]+g[la][i];
				mx=max(mx,f[x][j][k]);
			}
		}
		for (int j=1;j<=n;j++) f[x][j][0]=mx-c[j];
	}
	for (int j=1;j<=n;j++)
		for (int k=0;k<=p;k++)
			ans=max(ans,f[m%2][j][k]);
	printf("%d
",ans);
	return 0;
}