P3648 [APIO2014]序列分割

2021-03-20 08:26

阅读：668

标签：cpp 无法 getch 出现 return 想法特殊 tchar 通过

\(part1:\)

首先看到题目，嗯~ o(￣▽￣)o很骚

手玩一波样例之后发现状态很好想（这里简单地任务阶段可以被划分次数（也就是划分顺序）和划分位置来划分），初步想法是\(f[i][j]\)表示前\(i\)次最后一次切的是\(j\)位置

随后意识到没法通过上一层进行转移，这里出现问题也是正常，因为没有进行更深入地发掘性质

此处无法转移的原因是切的顺序不知道,真让人头大

\(part2:\)

观察到题目中计算分数的方法很骚，和的乘积

这两种运算都比较特殊，都有交换律

然后发现答案与切的顺序无关

\(part1\)中的问题迎刃而解，修正状态得:\(f[i][j]\)表示前\(i\)给数分成\(j\)段的最大值

\(part3:\)

开始转移

\(f[i][j]=min\{f[k][j-1]+s[k]*(s[i]-s[k]\}\)

\(s[i]\)时前缀和

复杂度：\(O(n^2*k)\)

得分：\(50\)
注意此代码中\(i\)和\(j\)的含义和上面反着，抱歉

#include
#define int long long int
using namespace std;
inline int read() {
    int f=1,s=0;
    char c=getchar();
    while(c'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c=1;--i)
    {
        t=road[i][t];
        cout

P3648 [APIO2014]序列分割

标签：cpp 无法 getch 出现 return 想法特殊 tchar 通过

原文地址：https://www.cnblogs.com/pyyyyyy/p/12305573.html

上一篇：C# 字母转数字

下一篇：题解【AcWing91】最短Hamilton路径

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：P3648 [APIO2014]序列分割
文章链接：http://soscw.com/index.php/essay/66629.html

亲，登录后才可以留言！

P3648 [APIO2014]序列分割

评论

热门文章

推荐文章

最新文章

置顶文章