1 条题解

  • 0
    @ 2021-07-17 11:37:49

    考虑动态规划,a[i]表示i分解最少个数:
    状态转移如下
    a[i+j^4] = min(a[i+j^4], a[j]+1)

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long int ll;
    int main()
    {
        int n;cin>>n;
        int a[n+1];for(int i=1;i<=n;i++) a[i]=111111;
        a[0]=0;
        for(int i=0;i<=n;i++)
        {
            for(int j=1;j<=20;j++)
            {
                if(i+j*j*j*j<=n) a[i+j*j*j*j] = min(a[i+j*j*j*j], a[i]+1); 
            }
        }  
        cout<<a[n];
        return 0;
    }
    
  • 1

信息

ID
1272
难度
6
分类
(无)
标签
(无)
递交数
81
已通过
20
通过率
25%
被复制
5
上传者