Bzoj3628: [JLOI2014]天天酷跑

3628: [JLOI2014]天天酷跑

Time Limit:?20 Sec??Memory Limit:?128 MB
Submit:?121??Solved:?44
[Submit][Status][Discuss]

Description

在游戲天天酷跑中，最爽的應該是超級獎勵模式了吧，沒有一切障礙，可以盡情的吃金幣，現在請你控制游戲角色來獲得盡可能多的分數。

游戲界面離散為一個長度為1~n，高度為1~m（初始點為（0，1））的矩陣圖。每個格子上都有收益（-1~1000），-1表示該點不能通過。游戲角色從起點一路奔跑向終點，中途可以跳躍來獲得更高的分數，在空中還能進行連跳。游戲開始前你可以設定跳躍的高度，以及能連跳的次數，初始跳躍高度為1，連跳數為1（最多為5），升級跳躍高度和連跳都需要一定的花費。跳躍高度設定完后游戲角色每次跳躍高度都將固定，連跳必須在下落過程中可以使用。所有操作都將在整點上完成，需要保證設定完的跳躍高度及連跳數，無法跳出游戲高度上限。

以下是連跳數為2連跳，跳躍高度為2的跳躍方案：

Input

第一行四個整數n，m，cost1，cost2。n，m如題意所示，cost1，cost2分別表示每升一級跳躍高度，連跳數所需的花費。

接下來m行，每行n個數。第i行第j個數表示地圖中高度為i，長度在第j列處的收益。

Output

如果無法跑出終點線，就輸出“mission failed”，否則輸出一行三個數，分別表示最大收益；及最大收益時，最小的連跳數；最大收益，最小連跳數時，最小的跳躍高度。

Sample Input

7 4 6 10
9 4 7 7 4 3 2
18 8 9 4 15 12 4
19 2 4 7 10 18 12
8 1 13 14 16 0 14

Sample Output

67 1 2

HINT

提示

20%數據滿足 m=2， n<=100000;

另有80%數據 n<=10000，2<m<=20，其中20%數據 2<n<=10，m<=10;

/*定義狀態f[i][j][o]表示處于x，y這個位置，還剩余o次連跳數的最大收益如果是跑——f[i][j][o]=max(f[i][j+1][o]+w[i][j]) w[i][j]為這點的權值；如果是跳的話——f[i][j][o]=max(f[i+跳躍高度（high）][j+high][o--]+hhh+w[i][j]) hhh跳躍上升過程中得到的金幣數。
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
#define inf 1<<30
#define maxn 100010
bool vis[25][maxn][6];
int f[25][maxn][6],map[25][maxn];
int n,m,c1,c2,ans=-inf,ans1,ans2,h,num;
int dfs(int x,int y,int now){if(x>n)return 0;if(map[y][x]==-1)return -inf;if(vis[y][x][now])return f[y][x][now];int tot=-inf,sum=0;bool flag=1;if(y==1)now=0;if(now<num){for(int i=1;i<h;i++){if(map[y+i][x+i]==-1){flag=0;break;}sum+=map[y+i][x+i];}if(flag)tot=max(tot,sum+dfs(x+h,y+h,now+1));}if(y==1)tot=max(tot,dfs(x+1,y,0));if(y>1)tot=max(tot,dfs(x+1,y-1,now));vis[y][x][now]=1;f[y][x][now]=tot+map[y][x];return f[y][x][now];
}
int main(){scanf("%d%d%d%d",&n,&m,&c1,&c2);for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)scanf("%d",&map[i][j]);for(num=1;num<=5;num++){for(h=1;h*num<m;h++){memset(f,-1,sizeof(f));memset(vis,0,sizeof(vis));int tot=dfs(0,1,m)-c2*(num-1)-c1*(h-1);if(ans<tot)ans=tot,ans1=num,ans2=h;}}if(ans>0)printf("%d %d %d",ans,ans1,ans2);else printf("mission failed");return 0;
}

?