讨论 / 写得很糊的记忆化搜索
wrongnumber 2015-11-30 01:16:02
点我顶贴 收藏 删除
#include<iostream>

#include<cstdio>

using namespace std;

char i;

int a[6][10],dp[6][10][101];

bool s[6][10][101];

int dfs(int ii,int jj,int rest)

{

if (s[ii][jj][rest]) return dp[ii][jj][rest];

if (ii==0) return 0;

s[ii][jj][rest]=true;

int ans=0;

for (int q=0;q<rest;q++)

for (int s1=0;s1<=q;s1++)

if (jj+q-s1<=9 && jj+q-s1-s1>=1)

ans=max(ans,dfs(ii-1,jj+q-s1-s1,rest-q-1)+a[ii][jj+q-s1]-a[ii][min(jj,jj+q-s1-s1)-1]);

else

if (jj-s1>=1 && jj-s1+q-s1<=9)

ans=max(ans,dfs(ii-1,jj+q-s1-s1,rest-q-1)+a[ii][max(jj,jj-s1+q-s1)]-a[ii][jj-s1-1]);

for (int s1=0,q=rest;s1<=q;s1++)

if (jj+q-s1<=9 && jj+q-s1-s1>=1)

ans=max(ans,a[ii][jj+q-s1]-a[ii][min(jj,jj+q-s1-s1)-1]);

else

if (jj-s1>=1 && jj-s1+q-s1<=9)

ans=max(ans,a[ii][max(jj,jj-s1+q-s1)]-a[ii][jj-s1-1]);

return dp[ii][jj][rest]=ans;

}

int ax,ay;

int n;

int main()

{

scanf("%d",&n);

for (int q=1;q<=5;q++)

for (int p=1;p<=9;p++)

{

cin>>i;

if (i=='K')

a[q][p]=1;

if (i=='L')

ax=q,ay=p;

a[q][p]+=a[q][p-1];

}

printf("%d\n",dfs(ax,ay,n));

return 0;

}

查看更多回复
提交回复