POJ 3186 Treats for the Cows —

　　第一眼感觉是贪心，，果断WA。然后又设计了一个两个方向的dp方法，虽然觉得有点不对，但是过了样例，交了一发，还是WA，不知道为什么不对= =，感觉是dp的挺有道理的，，代码如下（WA的）：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 using namespace std;

 const int N =  + ;

 int a[N];

 int dp[N][N];

 int n;

 int getDay(int i,int j)

 {

     return n - (j - i) + ;

 }

 int main()

 {

     while(scanf("%d",&n) == )

     {

         for(int i=;i<=n;i++) scanf("%d",a+i);

         memset(dp,,sizeof dp);

         for(int i=;i<=n;i++)

         {

             for(int j=i+;j<=n+;j++) dp[i][j] = max(dp[i][j], dp[i-][j] + getDay(i,j) * a[i]);

         }

         for(int j=n+;j>=;j--)

         {

             for(int i=j-;i>=;i--) dp[i][j] = max(dp[i][j], dp[i][j+] + getDay(i,j) * a[j]);

         }

         int ans = ;

         for(int i=;i<=n;i++) ans = max(ans, dp[i][i+]);

         printf("%d\n",ans);

     }

     return ;

 }

WA的DP

　　看了别人的博客以后，有一个不错的dp方法：dp[i][j]表示左边已经选了i个右边已经选了j个最大值，然后转移也很明显。AC代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 using namespace std;

 const int N =  + ;

 int a[N];

 int dp[N][N];

 int n;

 int main()

 {

     while(scanf("%d",&n) == )

     {

         for(int i=;i<=n;i++) scanf("%d",a+i);

         memset(dp,,sizeof dp);

         for(int i=;i<=n;i++)

         {

             for(int j=;i+j<=n;j++)

             {

                 if(i > ) dp[i][j] = max(dp[i][j], dp[i-][j] + a[i] * (i+j));

                 if(j > ) dp[i][j] = max(dp[i][j], dp[i][j-] + a[n-j+] * (i+j));

             }

         }

         int ans = ;

         for(int i=;i<=n;i++) ans = max(ans, dp[i][n-i]);

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

POJ 3186 Treats for the Cows ——（DP）

最新文章

热门文章