招行卡中心8.3笔试，第三题你是咋做的？

100，100，50. 最后一题只过了一半，用的dp，也知道自己时间复杂度过不了。后来想了想，感觉可以如下面方式优化.
f[k_][s_]表示将s_分为k_份的最大结果。显然对于同样的k_,这个是关于s_不减的函数。
f[k_][s_] = max(f[k_][s_], f[k_ -1][s_ - x] + x*(s_-x) ); 其中x表示第一刀切去的部分（后面不再分的）。
这里就是考虑怎么对x遍历的优化了。 后来我想了一下，感觉直觉上可以这样，对于s_, k_，第一刀最多切去s_/k_+1，为神马会这么感觉呢？因为对于直接对s_切成k_份后乘积最好的方式就是第一份为s_/k_+1或s_/k_，所以感觉这里同样，x再大就不划算了。。。这样我算了一下，对s=1000,最后计算次数大概在300w次,应该就能过了。

当然现在没有办法再验证了，要是有过的人也欢迎指正，告知对的做法。

#include 

using namespace std;

#define ll long long
#define mod 1000000007
#define PII pair
#define fi first
#define se second

int s;
int m;

int f[1005][1005];
// f[k_][s_] // divide to k_ parts, with s_
int fun()
{
    memset(f, 0 ,sizeof(f)); // default is 0
    for(int s_=1; s_<=s; s_++)
        f[1][s_] = s_;
    int k_=2;
    while(1)
    {
        if(k_>s) break;
        for(int s_=k_; s_<=s; s_++)
        {
            for(int x = 1; x<=s_/k_+1 ; x++)
                f[k_][s_] = max(f[k_][s_], f[k_ - 1][s_-x]+(s_-x)*x);
        }
        if(f[k_][s]>=m) break;
        k_++;
    }
    if(k_>s) return -1;
    return k_-1;
}

void work()
{
    cin>>s>>m;
    int ans=0;
//    for(int k_=2; k_<=1000; k_++)
//        for(int s_=k_; s_<=1000; s_++)
//            ans+=s_/k_; // if right, ans to see how many fps is needed
    cout<<ans<<endl;
    cout<<fun()<<endl;
}

#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
int main(int argc, char** argv)
{
#ifdef LOCAL
    fr("d:/tmp/input");
    fw("d:/tmp/output");
#endif
    std::ios::sync_with_stdio(false); // 是否与stdio兼容，printf,cout能保持一致
    std::cin.tie(0); // if not 0, cin will be flushed by cout
    work();

    return 0;
}