首页 > 代码库 > POJ 1651 (区间DP)
POJ 1651 (区间DP)
题目链接: http://poj.org/problem?id=1651
题目大意：加分取牌。如果一张牌左右有牌则可以取出，分数为左牌*中牌*右牌。这样最后肯定还剩2张牌。求一个取牌顺序，使得加分最少。
解题思路：
矩阵链乘的变种题。
假设有10、20、30、40、50五张牌。
如果我想要最后取30，则应该先取20、40，这样就还剩10、30、50三张牌了。
不难发现取20是dp[i][k]部分，取40是dp[k][j]部分，最后剩下的就是i、k、j三张牌。
DP边界：无
因为是算加分，区间间隔0、1的情况下dp[i][j]都无法加分，所以默认保留0即可，无须特别预处理。
最后ans=dp[1][n]。
#include "cstdio"#include "iostream"using namespace std;#define inf 0x3f3f3f3fint dp[105][105],card[105];int main(){ //freopen("in.txt","r",stdin); int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&card[i]); for(int p=2;p<=n;p++) { for(int i=1;i<=n-p;i++) { int j=i+p; dp[i][j]=inf; for(int k=i+1;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+card[i]*card[k]*card[j]); } } printf("%d\n",dp[1][n]); return 0;}
| 13156701 | neopenx | 1651 | Accepted | 176K | 0MS | C++ | 664B | 2014-07-24 14:03:01 |
POJ 1651 (区间DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。