首页 > 代码库 > TYVJ1124 花店橱窗

TYVJ1124 花店橱窗

2024-07-28 11:45:46   217人阅读

　　　http://www.tyvj.cn/Problem_Show.aspx?id=1124

　　设状态dp[i][j] 为第i个花放入第j个瓶子里所能得到的最大价值  且  (i<=j<=i+m-n)

　　dp[i][j] = max{dp[i-1][k]  |  i-1<=k<j}  + a[i][j] （a[i][j]为第i个花放入第j个瓶的价值）

　　每次转移的时候记录下路径，输出的时候dfs回去就ok了~

　　

 

　　

 1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 #include <vector> 6 #include <cmath> 7 #include <string> 8 #include <map> 9 #include <iostream>10 using namespace std;11 typedef long long LL;12 const int maxn = 105;13 const int maxv = 1005;14 const int mod = 1e9+7;15 const int INF = 0x3f3f3f3f;16 int dp[maxn][maxn],a[maxn][maxn];17 int path[maxn][maxn];18 int n,m;19 void dfs(int i,int j)20 {21     if(i==1)22     {23         printf("%d ",j);24         return;25     }26     dfs(i-1,path[i][j]);27     printf("%d",j);28     if(i!=n)printf(" ");29 }30 int main()31 {32 //    freopen("in.txt","r",stdin);33     while(cin>>n>>m)34     {35         for(int i = 1;i<=n;++i)36             for(int j = 1;j<=m;++j)37                 scanf("%d",&a[i][j]);38         memset(dp,0,sizeof(dp));39         memset(path,-1,sizeof(path));40         int x = m-n;41         for(int i = 1;i<=n;++i)42         {43             int up = i+x;44             for(int j = i;j<=up;++j)45             {46                 dp[i][j] = dp[i-1][i-1]+a[i][j];47                 path[i][j] = i-1;48                 for(int k = i;k<j;++k)49                 {50                     if(dp[i][j]<dp[i-1][k]+a[i][j])51                     {52                         dp[i][j] = dp[i-1][k]+a[i][j];53                         path[i][j] = k;54                     }55                 }56             }57         }58         int ans = -INF,ans_x;59         for(int i = n;i<=m;++i)if(ans<dp[n][i])60         {61             ans = dp[n][i];62             ans_x = i;63         }64         cout<<ans<<endl;65         dfs(n,ans_x);66         puts("");67     }68     return 0;69 }

 

TYVJ1124 花店橱窗


联系
我们