http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3685
这道题刚开始想了其他很多思路，包括DP什么都没有头绪。当时还有40多分钟，就想要专心过这题了。
然后就写了复杂度为O(2^n)的程序，算出了前25个之后，发现从第15个开始，答案不是0就是1。
分析一下可以发现，改变正负号不改变结果奇偶性，当1 ~ n中奇数为奇数个时，答案就为奇数，不然就是偶数。
可以计算得到1^3 + 2^3 + ... + n^3 = n^2 * (n+1)^2 / 4
如果n>=15时，假如答案不是0就是1这点成立，等价于从1^3 , 2^3 , 3^3 , ... , n^3中选取一些数字，使得和为 n^2 * (n+1)^2 / 8（取整）有解。
整数拆分问题！！当然不能用dp的方法做，抱着试试的心理写了裸的dfs，然后就过了。这应该是说明解的数量非常多吧。
n<15的所有情况，都可以暴力枚举算出来，我直接打表写在程序里了。
当然，我现在无法证明，为什么大于14的时候一定会有解，找到的话，会添加到这里。
代码如下：
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 typedef long long ll; 5 const char ans[20][20]={ 6 "", 7 "+", 8 "-+", 9 "-++", 10 "-+++", 11 "-++++", 12 "-+++-+", 13 "+---+++", 14 "+--+--++", 15 "+--+-+--+", 16 "-+-+++++++", 17 "-++-+--++++", 18 "+--++---+-++", 19 "--+++++-+++++", 20 "-++-+--++--+-+" 21 }; 22 char s[10010]; 23 ll s3[10010];//预处理三次方 24 bool dfs(ll sum,int n){ 25 for(int i=n;i>0;i--)if(sum>=s3[i]){ 26 if(sum - s3[i]==0 || dfs(sum - s3[i],i-1)){ 27 s[i-1]='+'; 28 return true; 29 } 30 } 31 return false; 32 } 33 void solve(ll n){ 34 for(int i=0;i<n;i++)s[i]='-'; 35 ll sum=n*n*(n+1)*(n+1)/8; 36 dfs(sum,n); 37 for(int i=n-1;i>=0;i--)putchar(s[i]); 38 puts(""); 39 } 40 int main() 41 { 42 for(ll i=1;i<=10000;i++) s3[i]=i*i*i; 43 int n; 44 while(~scanf("%d",&n)){ 45 if(n<15)puts(ans[n]); 46 else solve(n); 47 } 48 return 0; 49 }
做这场月赛的时候在最后两分钟，调出来过了，绝杀。。爽