3810: [Coci2015]Stanovi

Description

 

Input

输入一行，三个整数，n, m, k

 

 

Output

输出一个数，表示最小不满意度。

 

Sample Input

3 3 2

Sample Output

1

【Hint】

见描述中的左图的分割方案，最小不满意度为4 * (2 - 2) ^ 2 + (1 - 2) ^ 2 = 1。

【数据范围】

n, m <= 300

k <= 10000

HINT

 

Source

---

dp

f[x][y][u][d][l][r]表示x*y的矩阵且边的临接情况

u=1表示上面连接了，0表示没有连接

d是下面，l r是左右

初值是(xy-K)^2

在合法范围内转移即可

1 /************************************************************** 2     Problem: 3810 3     User: white_hat_hacker 4     Language: C++ 5     Result: Accepted 6     Time:6192 ms 7     Memory:12448 kb 8 ****************************************************************/ 9  10 #include
     
      11 #include
      
       12 #include
       
        13 #include
        
         14 #define MAXN 30515 #define ll long long16 using namespace std;17 int n,m,k;18 ll f[MAXN][MAXN][2][2][2][2];19 ll dp(int x,int y,int u,int d,int l,int r){20     if(x