PHP8.1.21版本已发布
vue8.1.21版本已发布
jquery8.1.21版本已发布
首页
课程
路径
文章
PHP培训
精品课
下载

技术文章  >  web前端 > html教程

Codeforces Round #267 (Div. 2) C George and Job_html/css_WEB-ITnose

原创
2016-06-24 11:57:19 1010浏览

题目大意：从n个数中选出m段不相交的子串，子串的长度均为k，问所有选出来的子串的所有数的和最大为多少。

DP题，DP还是太弱，开始时的dp方程居然写成了O(n^3)...  

dp[i][j]:  以num[i]结尾的序列，分成j段的最大和

dp[i][j]=max(dp[k][j-1]+sum[i]-sum[i-m])  这样的话，其实只要第一重循环是选的段数，第二重循环时数字个数

我又换了种思路

dp[i][j]: 前i个数，分成j段的最大和

dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+sum[i]-sum[i-m])

思路：二维嘛，所以写出来的dp方程肯定是要么从第一维变化转移过来的，要么从第二维的变化转移过来的


AC代码：

//#pragma comment(linker, "/STACK:102400000,102400000")#include #include #include #include #include #include #include #include #include #include using namespace std;#define ls(rt) rt*2#define rs(rt) rt*2+1#define ll long long#define ull unsigned long long#define rep(i,s,e) for(int i=s;i>1;const double EPS = 1e-8;const double pi = acos(-1);const int INF = 100000000;const int MAXN = 5000+100;ll num[MAXN],dp[MAXN][MAXN],pp[MAXN];int n,m,k;ll solve(){    CL(dp,0);    for(int i=m;i  
 第一种思路的AC代码（摘自 http://blog.csdn.net/qian99/article/details/39397101）：  

  
  
#include  #include  #include  #include  #include  #include  #include  #include  #include  #include  #include  #define inf 0x3f3f3f3f  #define Inf 0x3FFFFFFFFFFFFFFFLL  #define eps 1e-8  #define pi acos(-1.0)  using namespace std;  typedef long long ll;  const int maxn = 5000 + 5;  int a[maxn];  ll sum[maxn],dp[maxn][maxn],maxv[maxn];  int main()  {  //    freopen("in.txt","r",stdin);  //    freopen("out.txt","w",stdout);      int n,m,k;      scanf("%d%d%d",&n,&m,&k);      for(int i = 1;i = 0)              {                  dp[i][j] = max(dp[i][j],maxv[i-m] + sum[i] - sum[i-m]);              }          }          for(int i = 1;i
PHP课程HTML视频教程CSS视频JS视频教程Vue视频教程
声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn核实处理。
上一条：HEXO 指定404页面_html/css_WEB-ITnose 下一条：CSS3之图片3D翻转效果(网页效果每日一更)_html/css_WEB-ITnose

相关文章

查看更多
  • 热门课程
打开APP，随时随地在线学习！