考察:完全背包dp
人傻了,本来还想先用二维,结果没写出来,一脸懵逼看了题解.题解全是一维,最后发现是我f[i][j] = min(f[i-1][j],f[i][j-i*i]+1)的第二个i写成了i-1,板子背错了= =
这道题的物品体积是i*i,价值是1.这样才能算出个数来
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 const int N = 10010; 7 int f[N]; 8 int main() 9 { 10 memset(f,0x3f,sizeof f); 11 f[0] = 0; 12 for(int i=1;i<N;i++) 13 for(int j=i*i;j<N;j++) 14 f[j] = min(f[j],f[j-i*i]+1); 15 int T,kcase = 0; 16 scanf("%d",&T); 17 while(T--) 18 { 19 int n; 20 scanf("%d",&n); 21 printf("Case #%d: %d\n",++kcase,f[n]); 22 } 23 return 0; 24 }