POJ 1260-Pearls（DP） - c++编程基础

T); while(T--) { scanf("%d",&n); s[0]=0; for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&p[i]); s[i]=s[i-1]+a[i]; } dp[0]=0; for(int i=1;i<=n;i++) { dp[i]=dp[i-1]+(a[i]+10)*p[i]; for(int j=0;j

2.从后往前推。因为对于最后一种状态n，要从前面的n-1种状态中倒着连续合并。

#include 
                   
                    
#include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         #include 
                        
                          #include 
                         
                           #include 
                          
                            #include 
                           
                             #include 
                            
                              #include 
                             
                               #include 
                               #include 
                               
                                 #define ll long long #define maxn 116 #define pp pair
                                





                                  #define INF 0x3f3f3f3f #define max(x,y) ( ((x) > (y))   (x) : (y) ) #define min(x,y) ( ((x) > (y))   (y) : (x) ) using namespace std; int n,a[110],p[110],dp[110],s[110]; int dfs(int x) { if(x<1)return 0; if(dp[x]>=0)return dp[x]; if(x==1)return dp[x]=(a[x]+10)*p[x]; dp[x]=(a[x]+10)*p[x]+dfs(x-1); for(int i=x-1;i>=1;i--) dp[x]=min(dp[x],dfs(i-1)+(s[x]-s[i-1]+10)*p[x]); return dp[x]; } int main() { int T; scanf("%d",&T); while (T--) { s[0]=0; memset(dp,-1,sizeof(dp)); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&p[i]); s[i]=s[i-1]+a[i]; } printf("%d\n",dfs(n)); } return 0; }

POJ 1260-Pearls（DP）(二)