首页 > 其他分享 >题解:P11248 [GESP202409 七级] 矩阵移动

题解:P11248 [GESP202409 七级] 矩阵移动

时间:2024-11-09 17:41:13浏览次数:3  
标签:ch GESP202409 int 题解 sum P11248 max top dp

笑点解析:这个人所在城市考试当天刮台风了,没考,免费送了一次 12 月的考试。


设计这么一个东西:

\(dp_{i,j}\) 表示到格子 \((i, j)\) 的最大分数。

本来还好,但现在的问题是,如果这个格子是‘?’,我哪儿知道到底可不可以变啊?万一变得太多了,那,那不就废了!万一少了,那我分不就没了?

所以我们需要到底还剩多少次机会呢?不好办,没法儿处理。

其实加一维记录就可以了。

于是我得到了这个状态:

\(dp_{i, j, k}\) = 到格子 \((i, j)\) 且已经使用了 \(k\) 次机会的最大值。

转移也很好推:

不是‘?’:

\[dp_{i, j, k} = \begin{cases} \max(dp_{i, j - 1, k}, dp_{i - 1, j, k}) + 1& (i, j) = 1\\ \max(dp_{i, j - 1, k}, dp_{i - 1, j, k})& (i, j) = 0\\ \end{cases} \]

就是从两种可能的上一步转移过来,注意横竖均可。

是‘?’:

\[dp_{i, j, k} = \begin{cases} \max(dp_{i, j - 1, k}, dp_{i - 1, j, k}) + 1& k = 0\\ \max(dp_{i, j - 1, k - 1}, dp_{i - 1, j, k - 1}) + 1& k > 0\\ \end{cases} \]

同上,注意 \(k = 0\) 时不能使用机会。而且可以变的话当然是变了更好,所以 \(k > 0\) 时可以无脑使用。


ACCode:

/*Code by Leo2011*/
#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define EPS 1e-8
#define FOR(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define log printf
#define IOS                      \
	ios::sync_with_stdio(false); \
	cin.tie(nullptr);            \
	cout.tie(nullptr);

using namespace std;

typedef __int128 i128;
typedef long long ll;
typedef pair<ll, ll> PII;

const int N = 510, M = 310;
int m, n, t, x, a[N][N], dp[N][N][M], ans;  // dp[i][j][k] = (1, 1) 到(i, j),已经使用了k次机会的最大值
string s;

template <typename T>

inline T read() {
	T sum = 0, fl = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

template <typename T>

inline void write(T x) {
	if (x < 0) {
		putchar('-'), write<T>(-x);
		return;
	}
	static T sta[35];
	ll top = 0;
	do { sta[top++] = x % 10, x /= 10; } while (x);
	while (top) putchar(sta[--top] + 48);
}

int main() {
    IOS;
    cin >> t;
    while (t--) {
        cin >> n >> m >> x;
        FOR(i, 1, n) {
            cin >> s;
            for (int j = 0;j < m;++j) {
                if (s[j] == '?') a[i][j + 1] = -INF;
                else a[i][j + 1] = s[j] - '0';
            }
        }
        FOR(i, 1, n) FOR(j, 1, m) FOR(k, 0, x) {
              // 要用到 k - 1, 必须正序遍历。
            switch(a[i][j]) {
                case -INF:
                    if (k > 0) dp[i][j][k] = max(dp[i][j - 1][k - 1], dp[i - 1][j][k - 1]) + 1;
                    else dp[i][j][k] = max(dp[i][j - 1][k], dp[i - 1][j][k]);
                    break;
                case 1:
                    dp[i][j][k] = max(dp[i][j - 1][k], dp[i - 1][j][k]) + 1;
                    break;
                case 0:
                    dp[i][j][k] = max(dp[i][j - 1][k], dp[i - 1][j][k]);
                    break;
            }
        }
        FOR(i, 0, x) ans = max(ans, dp[n][m][i]);  // 不超过就是不一定,要遍历一遍
        cout << ans << endl;
        memset(dp, 0, sizeof(dp));
        memset(a, 0, sizeof(a));
        ans = -INF;
        // 多组数据要清空
    }
	return 0;
}

AC 记录~

标签:ch,GESP202409,int,题解,sum,P11248,max,top,dp
From: https://www.cnblogs.com/leo2011/p/18537022

相关文章

  • agc032 A~E 题解
    a倒推,每次删掉最后一个b[i]=i的即可b一开始发现可以构造完全二分图,使两边和同为S,这样每个点的和=对面二分图点的和=S,然后n=6和为奇数进一步发现可以直接分成A组组内和为B的组,然后组之间连边,此时S=(A-1)B,有AB=n(n+1)/2当n为奇数时取A=(n+1)/2,B=n,n单独一组其他大匹配小;n为偶数......
  • NOIP集训 P11071 「QMSOI R1」 Distorted Fate 题解
    题解:P11071「QMSOIR1」DistortedFate给定一个长度为\(n\)的数组\(A\),你需要完成以下\(q\)次操作。1.1lrx将\(A_i(l\lei\ler)\)异或上\(x\)。2.2lr求:\[(\sum_{i=l}^r\bigcup_{j=l}^iA_j)\bmod2^{30}\]其中\(\bigcup\)表示按位或。Input第一行输入......
  • [COCI2022-2023#5] Slastičarnica 题解
    前言题目链接:洛谷。题意简述一个长为\(n\)的序列\(\{a_n\}\)和\(q\)次操作,第\(i\)次操作中,你可以删除序列长为\(d_i\)的前缀或后缀,并需要保证删除的所有数\(\geqs_i\)。每次操作前,你可以选择任意长度的前缀或后缀,并将其删除,也可以不操作。请问,在你不能进行下一次操......
  • CodeforceTon Round 4 div1 + div2 题解
    题解A-EDreamissofar~A.BeautifulSequence检查每一位对应的数字是否小于等于位置,如果可以说明这个数字可以移动到对应位置上,遍历即可#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidsolve(){ intn; cin>>n; vector<int>a......
  • CF607B Zuma 题解
    CF607BZuma不知道为什么你谷会评蓝,这不是很基础的区间DP吗。Problem-607B-Codeforces题意简述消除回文子串的最小次数。思路对于区间\([i,j]\),如果它是回文的,那么消除它所需的次数是\(1\)。如果它不是回文的,但是\(a[i]==a[j]\),那么当区间\([i+1,j-1]\)被消除到只剩下......
  • [ARC158C] All Pair Digit Sums 题解
    C-AllPairDigitSums题意:设\(f(x)\)为\(x\)的数字和。例如\(f(158)=1+5+8=14\)。给定一个长度为\(N\)的正整数序列\(A\),求\(\sum_{i=1}^{N}\sum_{j=1}^{N}f(A_i+A_j)\)。分析:首先明确\(f(x)\)为\(x\)的数位和。举例情况:若有两个数分别为:\(12,21\)。\[f(......
  • QT中大量数据存储至excel的问题解决
            因为这个问题困扰了我很久,所以在这里记录一下,顺便给可能会遇到类似问题的人提供一点帮助。        在qt中,如果用C++处理数据保存到excel,正常来说在pro文件中添加axcontainer 然后就能够调用到excel,但是这只能适用于数量级没那么大时的需求。  ......
  • ffmpeg问题解决:Unrecognized option 'preset'. Error splitting the argument list: O
    来到这里,十有八九是手动编译安装的ffmpeg,在跑视频流程序或命令时出现这个问题。跟这个报错:ffmpeg:errorwhileloadingsharedlibraries:libx264.so.164:cannotopensharedobjectfile:Nosuchfileordirectory的错误本质是一样的,都是由于ffmpeg时使用到了libx264,而在......
  • 讲座の题解
    讲座配套题单的题解喵每题的文字解释会逐渐补充,如果有疑问直接私信喵目录讲座配套题单的题解喵目录A-看看你会不会用电脑B-求求你不要用内置函数C-GPAD-minE-for循环大神F-居然有人说这个是线性代数G-高三同学秒了H-无穷级数I-不要用内置函数......
  • 【题解】「NOIP2024模拟赛24 T3」钙绿
    【题解】「NOIP2024模拟赛24T3」钙绿https://www.becoder.com.cn/contest/5715/problem/3\(\mathcal{Description}\)给定\(n,p,m\)。对于每个\(k=0,1,\dots,m\),统计满足下面条件的\(n\)位\(10\)进制数:(允许前导零各位数之和不超过\(k\)。\(p\)能整除这个数。数据......