索鸟网

  1. 首页
  2. bzoj 3810: [Coci2015]Stanovi 动态规划

bzoj 3810: [Coci2015]Stanovi 动态规划


题意

这里写图片描述
n,m<=300

分析

这题有个结论就是如果一定要靠墙的话,那么一个矩形一定会被横着或竖着切成两个。
这个结论看上去感觉不是那么的显然,我也不会严格的证明。反正能过。。。
那么就可以大力dp了。设f[x,y,a,b,c,d]表示长宽以及上下左右是否为边界即可。
需要卡常。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N=305;
const LL inf=(LL)1e15;

int n,m,k;
LL f[N][N][2][2][2][2];

LL sqr(int x)
{
    return (LL)x*x;
}

void updata(LL &x,LL y)
{
    x=y<x?y:x;
}

LL solve(int x,int y,int a,int b,int c,int d)
{
    if (x>y) swap(x,y),swap(a,c),swap(b,d);
    if (f[x][y][a][b][c][d]>-1) return f[x][y][a][b][c][d];
    if (a+b+c+d==0) return inf;
    f[x][y][a][b][c][d]=sqr(k-x*y);
    if (a+c+d>0&&b+c+d>0)
        for (int i=1;i<=x;i++)
            updata(f[x][y][a][b][c][d],solve(i,y,0,a,c,d)+solve(x-i,y,0,b,c,d));
    if (c+a+b>0&&d+a+b>0)
        for (int i=1;i<=y;i++)
            updata(f[x][y][a][b][c][d],solve(x,i,a,b,0,c)+solve(x,y-i,a,b,0,d));
    return f[x][y][a][b][c][d];
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    memset(f,-1,sizeof(f));
    printf("%lld",solve(n,m,1,1,1,1));
    return 0;
}

来源地址:http://blog.csdn.net/qq_33229466/article/details/78230746 版权归作者所有!

相关教程

  • [DP] [BZOJ3810] [Coci2015]Stanovi

    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 一开始没怎
  • BZOJ 1222 [HNOI2001]产品加工 动态规划

    Description 某加工厂有A、B两台机器,来加工的产品可以由其中任何一台机器完成,或者两台机器共同完成。由于受到机器性能和产品特性的限制,不同的机器加工同一产品所需的时间会不同,若同时由两台机器共同进行加工,所完成任务又会不同。某一天,加工厂接到n个产品加工的任务,每个任务的工作量不尽一样。你的任务就是:已知每个任务在A机器上加工所需的时间t1,
  • BZOJ 1207 [HNOI2004]打鼹鼠 动态规划

    Description 鼹鼠是一种很喜欢挖洞的动物,但每过一定的时间,它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏:在一个n*n的网格中,在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠,如果i时刻鼹鼠在某个网格中出现,而机器人也处于同一网格的
  • Cool(动态规划)

    Cool (LYOI20171011模拟赛第一试第三题) (cool.* 时间空间限制: 1S, 128M) 题目描述: Tky 来到一个雄奇的金字塔挖宝,但是这是一座被诅咒的金字塔, Tky 必须马上逃离这里, 否则 Tky 就会被埋在金字塔里,但他不希望此行落空。 现在 Tky 面前有 N+1 种财宝,每种财宝都有一个价值。第一种财宝重量为 0,第二种财 宝重量为 1,总之第 I
  • 动态规划 - 背包问题

    package genius.base; public class PackageAnswer { /** * @param m 表示背包的最大容量 * @param n 表示商品的个数 * @param w 表示商品重量数组 weight * @param p 表示商品价值数组 price */
  • 动态规划方法总结

    动态规划方法总结 本文转自:http://blog.csdn.net/y990041769/article/details/24388913 按状态类型分 写在前面: 从状态类型分,并不表示一题只从属于一类。其实一类只是一种状态的表示方法。可以好几种方法组合成一个状态,来解决问题。 1.1. 编号(长度)动态规划共性总结: 本类的状态是
  • hdu1300 重温世界杯【动态规划】

    解题思路: 把环拆成2*n的序列,不断减去左边界,加上右边界更新即可。 #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cmath>
  • 【动态规划】[luoguP1417]烹调方案

    题目 我们要先推一个贪心 考虑相邻的两个物品xy 已经耗费p的时间 先做x a[x]−(p+c[x])∗b[x]+a[y]−(p+c[x]+c[y])∗bya[x]-(p+c[x])*b[x]+a[y]-(p+c[x]+c[y])*by ————① 先做y a[y]−(p+c[y])∗b[y]+a[x]−(p+c[y]+c[x])∗bxa[y]-(p+c[y])*b[y]+a[x]-