局域网内部如何做网站,网站建立平台,做网站 以图搜货,网站推广多少钱一年P1437 [HNOI2004]敲砖块
题意#xff1a;
在一个凹槽中放置了 n 层砖块、最上面的一层有 n 块砖#xff0c;从上到下每层依次减少一块砖。每块砖都有一个分值#xff0c;敲掉这块砖就能得到相应的分值#xff0c;如下图所示#xff1a;
14 15 4 3 2333 33 76 22 …P1437 [HNOI2004]敲砖块
题意
在一个凹槽中放置了 n 层砖块、最上面的一层有 n 块砖从上到下每层依次减少一块砖。每块砖都有一个分值敲掉这块砖就能得到相应的分值如下图所示
14 15 4 3 2333 33 76 22 13 1122 2331如果你想敲掉第 i 层的第 j 块砖的话若 i1你可以直接敲掉它若 i1则你必须先敲掉第 i-1 层的第 j 和第 j1 块砖。 你现在可以敲掉最多 m 块砖求得分最多能有多少。
题解
很明显是动态规划刚开始设的状态为dp[i][j][k]表示敲第k块砖敲到(i,j)的最大值。但是这样设并没办法求因为动态规划是无后效性的而这么设我们需要考虑之前的选择情况 现在就尬住了无论从上往下还是从下往上都存在后效性影响那我们可以从左往右推或者从右往左推 我们开始考虑从右往左推如果我想打砖块(x,y),我必须将其正上方和右上角的砖块都打了正上方的砖块是打掉(x,y)所要考虑的而右上角的砖块可以是由右侧的砖块打掉考虑的 什么意思看图 现在我们想打蓝色砖块(2,1),两个橙色部分必须已经被打掉了和蓝色砖块同列的砖块是我们本次要打掉的而右上角的砖块(1,2),我们可以通过状态转移而来因为我们是从右往左处理右边就已经都处理完了那么(3,2)紫色砖块的情况已经处理完了如果紫色砖块要打其上侧的(1,2)砖块也一定是打好的所有我们就可以由第i1列的状态转移到第i列的状态 也就是说当处理(i,j)时本列的砖块需要我们现处理而右上角的砖块可以前一列(j1列的状态得到 这样处理无后效性 这样就得到 dp[i][j]maxi−1pn−i(dp[p][j1])∑p1ia[p][j]dp[i][j]max_{i-1pn-i}(dp[p][j1])\sum_{p1}^ia[p][j]dp[i][j]maxi−1pn−i(dp[p][j1])p1∑ia[p][j] 我们再将敲砖块的数量考虑进去 设dp[i][j][k]:表示已经敲了k个砖块且第k个敲的是(i,j)的最大得分情况 dp[i][j][k]maxi−1pn−i(dp[p][j1][k−i])∑p1ia[p][j]dp[i][j][k]max_{i-1pn-i}(dp[p][j1][k-i])\sum_{p1}^ia[p][j]dp[i][j][k]maxi−1pn−i(dp[p][j1][k−i])p1∑ia[p][j]
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn55;
int dp[maxn][maxn][3020];
int a[maxn][maxn];
int sum[maxn][maxn];
int main()
{//rd_test();int n,m;read(n,m);for(int i1;in;i){for(int j1;jn-i1;j){cina[i][j];}}for(int i1;in;i){for(int j1;jn-i1;j){sum[j][i]sum[j-1][i]a[j][i];}}memset(dp,-127,sizeof(dp));dp[0][n1][0]0;int ans0;for(int jn;j1;j--){//列 for(int i0;in-j1;i){//行 for(int ki;km;k){for(int pmax(0,i-1);pn-j;p){if(dp[p][j1][k-i]!-1){dp[i][j][k]max(dp[i][j][k],dp[p][j1][k-i]sum[i][j]);ansmax(ans,dp[i][j][k]);}}}}}coutans;//Time_test();
}
