点击打开链接
思路: 动态规划
分析:
1 题目要求找到最大的美学值,并且要求标识号大的必须在标识号小的右边,那么这就可以知道,如果花朵i在第i行的第j列那么第i+1朵必须在j+1后面
2 很明显的阶段就出来了,我们用dp[i][j]表示第i朵花放在第j列能够得到的最大美学值,那么dp[i][j] = max(dp[i-1][j]) + num[i][j];这里注意每一多花可以放的区间,第i多花可以放的区间就是第i行的[i~V-F+n]
3 题目要求输出没多花的位置,那么就是在状态转移的时候记录一下位置即可
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 1<<30;
const int MAXN = 110;
int n , m;
int num[MAXN][MAXN] , dp[MAXN][MAXN];
int path[MAXN][MAXN] , output[MAXN];
void solve(){
for(int i = 1 ; i <= m-n+1 ; i++)
dp[1][i] = num[1][i];
memset(path , -1 , sizeof(path));
for(int i = 2 ; i <= n ; i++){
for(int j = i ; j <= m-n+i ; j++){
dp[i][j] = num[i][j];
int Max = -INF;
int pos;
for(int k = i-1 ; k < j ; k++){
if(dp[i-1][k] > Max){
Max = max(Max , dp[i-1][k]);
pos = k;
}
}
dp[i][j] += Max;
path[i][j] = pos;
}
}
int ans = -INF;
int pos , x , y;
for(int i = n ; i <= m ; i++){
if(ans < dp[n][i]){
ans = max(ans , dp[n][i]);
y = i;
}
}
printf("%d\n" , ans);
pos = n-1;
x = n;
output[pos--] = y;
while(path[x][y] != -1){
output[pos--] = path[x][y];
y = path[x--][y];
}
printf("%d" , output[0]);
for(int i = 1 ; i < n ; i++)
printf(" %d" , output[i]);
printf("\n");
}
int main(){
while(scanf("%d%d" , &n , &m) != EOF){
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= m ; j++)
scanf("%d" , &num[i][j]);
solve();
}
return 0;
}
分享到:
相关推荐
rqnoj的一些资料 c++的绝对对你有用。。。。。。
rqnoj ,题库。 密码锁(月赛) 动态规划,dp
很好的东西!省事省力省距离!免费啊免费啊
典型的排列组合题,几乎不需要什么解释。rqnoj第22题,程序写的很简练,初学者想想就懂了。
标程,有c++和Pascal版的。cena测试通过。RQNOJ测试通过。
Leetcode本项目使用的题库为 :star:主要使用Java书写算法,还有部分SQL语句练习,刚刚开始刷题,数量并不是很多 :grinning_face_with_sweat:我就不建翻译...TK题库 ATcoder 紫外线 RQNOJ YO玲珑学院 OJ彗星评测鸭 厨师