题目训练网址（密码hpuacm） ： https://vjudge.net/contest/245961#overview
矩阵取数问题
一个N*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。
例如：3 * 3的方格。
1 3 3
2 1 3
2 2 1
能够获得的最大价值为：11。
Input
第1行：N，N为矩阵的大小。(2 <= N <= 500)
第2 - N + 1行：每行N个数，中间用空格隔开，对应格子中奖励的价值。（1 <= Nii <= 10000)
Output
输出能够获得的最大价值。
Sample Input
3
1 3 3
2 1 3
2 2 1 Sample Output
11 思路： 动态规划的思想，每一个状态都选上一个状态中的较大值，dp[i]][j] 表示的是从起点到 i，j 点能获得的最大值。
状态转移方程 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + num[i][j];
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500+10;
int num[MAXN][MAXN];
int dp[MAXN][MAXN];
int main()
{
int n;
while( scanf("%d", &n) != EOF )
{
for( int i=1; i<=n; i++ )
{
for( int j=1; j<=n; j++ )
scanf("%d", &num[i][j]);
}
memset(dp, 0, sizeof(dp));
dp[1][1] = num[1][1];
for( int i=1; i<=n; i++ )
{
for( int j=1; j<=n; j++ )
{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + num[i][j];
}
}
printf("%d\n", dp[n][n]);
}
return 0;
} 矩阵取数问题 V2
一个M*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。
例如：3 * 3的方格。
1 3 3
2 1 3
2 2 1
能够获得的最大价值为：17。1 -> 3 -> 3 -> 3 -> 1 -> 2 -> 2 -> 2 -> 1。其中起点和终点的奖励只计算1次。
Input
第1行：2个数M N，中间用空格分隔，为矩阵的大小。(2 <= M, N <= 200)
第2 - N + 1行：每行M个数，中间用空格隔开，对应格子中奖励的价值。(1 <= Ai,ji,j <= 10000)
Output
输出能够获得的最大价值。
Sample Input
3 3
1 3 3
2 1 3
2 2 1 Sample Output
17 与上一个问题多相似，没招了么？其实我们可以“两个人一起”dp（让两个人同时走）。
用dp[x1][y1][x2][y2]表示第一个人在(x1,y1) 并且第二个人在(x2,y2)时的最大值。
我们有初值dp[1][1][1][1] = a[1][1]，求的是dp[m][n][m][n]。
问题来了：每个人走一步，状态转移是什么？
dp[x1][y1][x2][y2] = maxfdp[x1'][y1'][x2'][y2']g + a[x1][y1] + a[x2][y2]
其中(x1',y1')是(x1,y1)的邻居，(x2',y2')是(x2,y2)的邻居。
事实上，因为我们有这个等式提示我们其实只要用3维就可以表
示这个矩阵，因为y2 = x1 + y1 { x2所以那一维可以用走多少
步表示出来。dp[step + 1][x1][x2] = maxfdp[step][x1'][x2']g + a[x1][y1] + a[x2][y2]
图中为step做了编号。
然而这个dp并没有体现出走到相同格子，数字仅计算一次的要求。那么我们加上这个条件：
如果x1 = x2，dp[step + 1][x1][x2] = maxfdp[step][x1'][x2']g + a[x1][y1]。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200 + 3;
int dp[MAXN*2][MAXN][MAXN];
int num[MAXN][MAXN];
int main()
{
int n, m;
while( ~scanf("%d%d", &m, &n) )
{
for( int i=1; i<=n; i++ )
{
for( int j=1; j<=m; j++ )
scanf("%d", &num[i][j]);
}
//memset(dp, 0, sizeof(dp));
//dp[0][0][0] = num[0][0];
for( int s = 2; s <= n+m; s++ )
{
for( int x1 = 1; x1 <= n ; x1++ )
{
for( int x2 = 1; x2 <= n; x2++ )
{
int y1 = s - x1;
int y2 = s - x2;
if( x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m
&& x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m )
{
dp[s][x1][x2] = max( max(dp[s-1][x1][x2], dp[s-1][x1-1][x2]),
max(dp[s-1][x1-1][x2-1], dp[s-1][x1][x2-1]) )
+ ( x1 == x2 && y1 == y2 ? num[x1][y1] : num[x1][y1] + num[x2][y2] );
}
}
}
}
printf("%d\n", dp[m+n][n][n]);
}
return 0;
} 注意step是走的第几步，其值等于上一个状态的x和y坐标值和。
子串查询
度度熊的字符串课堂开始了！要以像度度熊一样的天才为目标，努力奋斗哦！
为了检验你是否具备不听课的资质，度度熊准备了一个只包含大写英文字母的字符串 A[1,n]=a1a2⋯anA[1,n]=a1a2⋯an，接下来他会向你提出 qq 个问题 (l,r)(l,r)，你需要回答字符串 A[l,r]=alal+1⋯arA[l,r]=alal+1⋯ar 内有多少个非空子串是 A[l,r]A[l,r] 的所有非空子串中字典序最小的。这里的非空子串是字符串中由至少一个位置连续的字符组成的子序列，两个子串是不同的当且仅当这两个子串内容不完全相同或者出现在不同的位置。
记 |S||S| 为字符串 SS 的长度，对于两个字符串 SS 和 TT ，定义 SS 的字典序比 TT 小，当且仅当存在非负整数 k(≤min(|S|,|T|))k(≤min(|S|,|T|)) 使得 SS 的前 kk 个字符与 TT 的前 kk 个字符对应相同，并且要么满足 |S|=k|S|=k 且 |T|>k|T|>k，要么满足 k<min(|S|,|T|)k<min(|S|,|T|) 且 SS 的第 k+1k+1 个字符比 TT 的第 k+1k+1 个字符小。例如 "AA" 的字典序比 "AAA" 小，"AB" 的字典序比 "BA" 小。
Input
第一行包含一个整数 TT，表示有 TT 组测试数据。
接下来依次描述 TT 组测试数据。对于每组测试数据：
第一行包含两个整数 nn 和 qq，表示字符串的长度以及询问的次数。
第二行包含一个长为 nn 的只包含大写英文字母的字符串 A[1,n]A[1,n]。
接下来 qq 行，每行包含两个整数 li,rili,ri，表示第 ii 次询问的参数。
保证 1≤T≤101≤T≤10，1≤n,q≤1051≤n,q≤105，1≤li≤ri≤n1≤li≤ri≤n。
Output
对于每组测试数据，先输出一行信息 "Case #x:"（不含引号），其中 x 表示这是第 xx 组测试数据，接下来 qq 行，每行包含一个整数，表示字符串 A[l,r]A[l,r] 中字典序最小的子串个数，行末不要有多余空格。
Sample Input
1
2 3
AB
1 1
1 2
2 2 Sample Output
Case #1:
1
1
1 说了一大堆废话，其实就是让你找一个字母，有A就找A的个数,没有找B，26个字母肯定至少有一个字母出现。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 1e5+7;
char str[MAXN];
int sum[26+1][MAXN];
int main()
{
int t;
scanf("%d", &t);
int t1 = t; // t1 - t 就是第几组样例
while( t-- )
{
memset(sum, 0, sizeof(sum));
int n, q; // 字符串长度和询问次数
scanf("%d%d", &n, &q);
scanf("%s", str+1);
for( int i=1; i<=n; i++ ) // 记录前缀和
{
for( int j=0; j<26; j++ )
{
if( j + 'A' == str[i] )
sum[j][i] = sum[j][i-1] + 1; // 从前一个状态转移过来的
else
sum[j][i] = sum[j][i-1];
}
}
printf("Case #%d:\n", t1-t);
int li, ri; // 第i次询问的子串参数
int ans = 0;
for( int i=0; i<q; i++ )
{
scanf("%d%d", &li, &ri);
for( int j=0; j<26; j++ )
{
if( sum[j][ri] - sum[j][li-1] != 0)
{
ans = sum[j][ri] - sum[j][li-1];
break;
}
}
printf("%d\n", ans);
}
}
return 0;
} 说明一下， 这里用dp思想和打标的方法，把每个字母出现的次数都记录了下来。还有就是为什么是
ans = sum[j][ri] - sum[j][li-1]; 其实很好理解，每一个状态都来源于它前面的一个状态，再加上本身的值。所以当询问2到6的子串时如果用sum[0][6] - sum[0][2]那么就不包括2所在的状态，故应该是sum[0][6] - sum[0][1]；
Polycarp and Div 3
Polycarp likes numbers that are divisible by 3.
He has a huge number ss. Polycarp wants to cut from it the maximum number of numbers that are divisible by 33. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after mm such cuts, there will be m+1m+1 parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by 33.
For example, if the original number is s=3121s=3121, then Polycarp can cut it into three parts with two cuts: 3|1|213|1|21. As a result, he will get two numbers that are divisible by 33.
Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.
What is the maximum number of numbers divisible by 33 that Polycarp can obtain?
Input
The first line of the input contains a positive integer ss. The number of digits of the number ss is between 11 and 2⋅1052⋅105, inclusive. The first (leftmost) digit is not equal to 0.
Output
Print the maximum number of numbers divisible by 33 that Polycarp can get by making vertical cuts in the given number ss.
Examples
Input
3121
Output
2
Input
6
Output
1
Input
1000000000000000000000000000000000
Output
33
Input
201920181
Output
4
Note
In the first example, an example set of optimal cuts on the number is 3|1|21.
In the second example, you do not need to make any cuts. The specified number 6forms one number that is divisible by 33.
In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and 3333 digits 0. Each of the 3333 digits 0 forms a number that is divisible by 33.
In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers 00, 99, 201201 and 8181 are divisible by 33.
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
while( cin >> s )
{
int ans = 0;
int temp = 0;
for( int i=0; i < s.size(); i++ )
{
if( (s[i] - '0') % 3 == 0 )
{
ans ++;
continue;
}
if( i+1 < s.size() && ( s[i+1] - '0') % 3 == 0 )
{
ans ++, i++;
continue;
}
if( i+1 < s.size() && (s[i]+s[i+1] -'0' - '0') % 3 == 0 )
{
ans++, i++;
continue;
}
if( i+2 < s.size() )
ans++, i += 2;
}
printf("%d\n", ans);
}
return 0;
}
京公网安备 11010502036488号