[낙곡P1373] [문제풀이] 작은 a와 uim의 대탈출.

(나 시키지 마. 난 제목이 아니야)
이 문제는 dp라는 것을 쉽게 알 수 있다.
조금만 생각하면 yy가 괜찮은 컨디션을 낼 수 있다.
f[i][j][k][0/1]는 점(i, j), 막액량 차이 k(소a-uim=k), 소a/uim가 마지막으로 취한 상황수를 대표한다.
갱1:

f[850][850][20][2]:Accepted 100 2.00s 103.31MB
f[850][850][25][2]:Unaccepted 85 1.11s 125.00MB//MLE   

옮기기도 쉽다: 점 하나가 왼쪽이나 위에서 걸어올 수 있다

int tmp=(c-mp[i][j]+k)%k;
f[i][j][c][0]+=(f[i-1][j][tmp][1]%mod+f[i][j-1][tmp][1]%mod)%mod;
f[i][j][c][0]%=mod;            
tmp=(c+mp[i][j])%k;
f[i][j][c][1]+=(f[i-1][j][tmp][0]%mod+f[i][j-1][tmp][0]%mod)%mod;
f[i][j][c][1]%=mod;

그중 tmp는 이전 점의 막액차를 대표한다
갱2: 입력할 때의 막액량은 k보다 클 수 있다
갱3: 어느 한 점에서 출발할 수 있으며 각 f[i][j][mp[i][j][0]에 1을 부여해야 한다.
갱4: c-mp[i][j]는 마이너스일 수 있습니다. tmp=(c-mp[i][j]+k)%k가 아니라 tmp=(c-mp[i][j])%k라면,

Unaccepted 10 2.01s 103.01MB

더 이상 말하지 말고 코드를 보아라

 1 #include
 2 using namespace std;
 3 int n,m,k,mp[850][850];
 4 //  ：    
 5 int f[850][850][20][2],sum;
 6 #define mod 1000000007
 7 int main(){
 8     ios::sync_with_stdio(0);
 9     cin>>n>>m>>k;
10     k++;
11     //   
12     for(int i=1;i<=n;i++){
13         for(int j=1;j<=m;j++){
14             cin>>mp[i][j];
15             //  ：    
16             mp[i][j]%=k;
17             //  ：    
18             f[i][j][mp[i][j]][0]=1;
19         }
20     }
21     //DP
22     for(int i=1;i<=n;i++){
23         for(int j=1;j<=m;j++){
24             for(int c=0;c){
25                 //  ：   
26                 int tmp=(c-mp[i][j]+k)%k;
27                 f[i][j][c][0]+=(f[i-1][j][tmp][1]%mod+f[i][j-1][tmp][1]%mod)%mod;
28                 f[i][j][c][0]%=mod;
29                 
30                 tmp=(c+mp[i][j])%k;
31                 f[i][j][c][1]+=(f[i-1][j][tmp][0]%mod+f[i][j-1][tmp][0]%mod)%mod;
32                 f[i][j][c][1]%=mod;
33             }
34             sum=(sum+f[i][j][0][1])%mod;
35         }
36     }
37     cout<endl;
38     return 0;
39 }

꽃을 뿌리다