2012 ACM/ICPC Asia Regional Tianjin Online 1006_you are the one 解题报告
HDOJ 4283 You are the one
2012 ACM/ICPC Asia Regional Tianjin Online F 题
一道很悲情的DP题，比赛的时候没做出来，比赛结束后第17分钟才AC。
关键思想：最先进栈的元素最后出栈，例如第i个元素入栈，如果它最终的位置是在k，那么i 到 k 这一段中不可能有 k 位置后的数出现。
#include<cstdio>int dp[101][101][101],arr[101];int search(int s,int e,int k){ if(s==e) return arr[s]*k; if(s>e) return 0; if(dp[s][e][k]!=-1) return dp[s][e][k]; int min=search(s+1,e,k+1)+arr[s]*k; for(int i=s+1;i<=e;i++) { int l=search(s+1,i,k); int r=search(i+1,e,(k+i+1-s)); int temp=arr[s]*(k+i-s); int ts=l+r+temp; if(ts<min) min=ts; } dp[s][e][k]=min; return min;}int main(){ int t,n; scanf("%d",&t); for(int cas=1;cas<=t;cas++) { scanf("%d",&n); for(int i=0;i<n;i++){ for(int j=0;j<n;j++) { for(int k=0;k<n;k++) dp[i][j][k]=-1; } } for(int i=0;i<n;i++) scanf("%d",&arr[i]); search(0,n-1,0); printf("Case #%d: %d\n",cas,dp[0][n-1][0]); } return 0;}