1 条题解
-
0Takagi-san (njnu19200437) LV 10 MOD @ 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
- 上传者