先上代码
1.这题需要基础,需要dp背包的掌握,然后还得融会贯通,认出这是dp的题型。
2.还是刷题不够多啊! 还是继续努力。
#include<bits/stdc++.h>
using namespace std;
const int N = 410;
int f[21][N][N]; //21个物品,后面是两维背包限制:体积和重量(分别是p次方之和,个数)
int n, K, p;
//计算a的b次方,用来求i的p次方
int power(int a, int b){
int res =1;
while(b--) res *= a;
return res;
}
int main(){
cin >> n >> K >> p;
memset(f ,-0x3f, sizeof f); //初始化为负无穷,表示不存在
f[0][0][0] = 0; //初始条件,一个物品都没有,价值为0
int i;
//枚举所有的物品
for( i=1; ; i++){
int v = power(i ,p);// 物品i的体积:i的p次方
if(v > n) break; //背包体积n,已经装不下
for(int j = 0; j <= n; j++) //枚举f的第二维
for(int k =0; k<= K; k++) //枚举f的第三维:数的个数
{
f[i][j][k] = f[i-1][j][k];
//如果f[i][j-v][k-1]合法的话,就转移
if( j>= v && k)
f[i][j][k] = max(f[i][j][k], f[i][j-v][k-1]+i);
}
}
//退出for循环的条件是第一个不符合的i,所以合法的应该i-1
i--;
if(f[i][n][K] < 0) cout<<"Impossible";
//下面是倒序输出具体方案:
else{
cout<<n<<" = ";
bool is_first = true; //用来控制输不输出加号
//找方案:倒推,看怎么转移过来的,i选没选?选的话就输出
while(i){
int v = power(i, p); //体积
//如果选择了i:正推:如果选i价值则选i;反过来,如果选i价值大,代表已经选过,应该输出。
while(f[i][n-v][K-1] + i >= f[i-1][n][K]){
if(is_first) is_first =false;
else cout<<" + ";
printf("%d^%d",i,p); //i的p次方
n -= v ,K--; //体积--,数量--
}
i--; //i处理完了,倒退看看前面的选没选
}
}
}
在csdn上写的题解:反复粘贴太累了。
https://lishizheng.blog.csdn.net/article/details/113752291