N久没做过cf了,今天心血来潮搞了一个,唉,坑爹的D题,卡了N久
解题:
直接暴力
也是直接暴力
题目:
给定一个序列,给定一个块的大小m(必须为连续),给定k个块(不能交叉,只能顺序),求k块之和最大是多少。
简单DP,状态转移方程:
f[i][j] = max(f[i - 1][j], f[i - m][j - 1] + sum[i - m]);
其中i表示遍历原数组到i为止,j表示第j组(一共k组),sum[i - m]表示以i - m为开头的连续的块和
代码:
#include<iostream> #include<cstdio> #include<memory.h> #include<queue> #include<cmath> #include<stack> #include<cstdlib> #include<vector> #include<string> #include<cstring> #include<map> using namespace std; #define Clear(f, nr) memset(f, nr, sizeof(f)) const int SIZE = 5005; const int MSIZE = 10000; typedef long long ll; const int INF = 1 << 30; long long f[SIZE][SIZE]; long long sum[SIZE]; int a[SIZE]; int main() { int n, m, k; while(cin >> n >> m >> k) { for(int i = 0; i < n; i ++) cin >> a[i]; Clear(sum, 0); for(int i = 0; i < m; i ++) sum[0] += a[i]; for(int i = 1; i < n - m + 1; i ++) sum[i] = sum[i - 1] - a[i - 1] + a[i + m - 1]; for(int i = 0; i < n; i ++) f[i][0] = 0; f[m - 1][1] = sum[0]; for(int i = m; i < n; i ++) { for(int j = 1; j <= k; j ++) f[i][j] = max(f[i - 1][j], f[i - m][j - 1] + sum[i - m + 1]); } cout << f[n - 1][k] << endl; } }
给定一个字符串序列,求替换其中的字符串使得替换后的数据含单词r最少(忽略大小写),如果r一致,则输出长度最小的。
解题:
暴力搞得,一开始卡第六组数据,后来发现可以循环替换a->b->c....一直替换下去
结果还是卡第七组数据。。。。
我的思路就是替换 如果想要替换a为b
则b中要么r比a少,要么b字符串比a短。
后来发现思路是错的,根据第7组数据:
5 aa bb cc ee ff 5 aa a bb aa cc bb ee cc ff bb
按我的思路替换是不对的。
因为数据替换张成了一棵树,需要dfs遍历找到替换最优解(根据以上的替换规则,必为叶子结点)
完了dfs时再把中间压缩一下,中间节点直接map到最优叶子节点
由于中间过程存在环,还要强连通缩点,重构图。
代码写的太乱了,不发了。。。