HDU 1300 Pearls
凭直觉猜测了一下，写了一个DP，居然能AC。
dp[i][j]表示第i种到第n种物品都买完且最小的单价是第j种物品时候的最小总费用
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const long long INF=999999999999999; const int maxn=100+10; int T,n; long long dp[maxn][maxn]; long long a[maxn],c[maxn]; int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i],&c[i]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=INF; dp[n][n]=c[n]*(a[n]+10); long long Min=dp[n][n]; for(int i=n-1;i>=1;i--) { dp[i][i]=Min+c[i]*(a[i]+10); Min=dp[i][i]; for(int j=i+1;j<=n;j++) { if(dp[i+1][j]==INF) continue; dp[i][j]=dp[i+1][j]+c[j]*a[i]; Min=min(dp[i][j],Min); } } printf("%lld ",Min); } return 0; }