2019 Wannafly Winter Camp

---恢复内容开始---

day1:

　　比赛网址:https://www.zhixincode.com/contest/1

　　wlsnb!

　　2.吃豆豆:

　　dp[12][12][100010];dp[i][j][k]:在k秒时,i,j位置处得到的糖果

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=10010;
 4 int dp[12][12][maxn];
 5 int T[12][12];
 6 int n,m,c;
 7 int main()
 8 {
 9     for(int i=0;i<12;i++)for(int j=0;j<12;j++)for(int k=0;k<maxn;k++)dp[i][j][k]=-1e9;//初始化,dp最小值为-INF
10     cin>>n>>m>>c;
11     int sx,sy,ex,ey;
12     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>T[i][j];
13     cin>>sx>>sy>>ex>>ey;
14     dp[sx][sy][0]=0;//wls在初始位置的时候时没有糖果的
15 
16     for(int k=1;k<maxn;++k)
17     {
18         for(int i=1;i<=n;++i)
19         {
20             for(int j=1;j<=m;++j)
21             {
22                 //dp按时间作为层数转移
23                 dp[i][j][k]=max({dp[i][j][k-1],dp[i-1][j][k-1],dp[i+1][j][k-1],dp[i][j-1][k-1],dp[i][j+1][k-1]})+(k%T[i][j]==0?1:0);   
24             }
25         }
26     }
27     //在结束位置找最先满足条件的时间
28     for(int i=1;i<maxn;i++)
29     {
30         if(dp[ex][ey][i]>=c)
31         {
32             cout<<i<<endl;
33             return 0;
34         }
35     }
36 }