HDOJ 5691 Sitting in Line

2023-09-24 21 0

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5691

小编果然是个辣鸡,百度之星比赛过去好久了,现在在状态压缩的专题里看到这一题,才反应过来这道题是状态压缩=.=,现在看来,16的数据以及很明显的状态暗示,我居然都没有看出来……哎,果然还是太辣鸡了。

本体不仅要枚举用了几个的状态,还要枚举当前状态最后一个是什么才行,因为我们是要算出相邻两项的乘积的和,所以我们必须关注最后一位是什么,这样在加入新的点的时候我们就能直接加上这两个数的乘积即可。

那么我们枚举每一个状态下的最后一位i,再枚举此时下一个数j会是什么的所有情况,就能得到答案,状态转移方程为:dp[j][cur|(1<<j)] = max(dp[j][cur|(1<<j)], dp[i][cur] + a[i]*a[j])。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1<<17;
int dp[20][maxn],sta[20][maxn],a[20],p[20],cnt[20];
int main()
{int T,t=1,n;scanf("%d", &T);while(T--){printf("Case #%d:\n", t++);scanf("%d", &n);for(int i=0; i<n; i++)scanf("%d%d", &a[i], &p[i]);for(int i=0; i<n; i++)for(int j=0; j<(1<<n); j++)dp[i][j] = -INF;for(int i=0; i<n; i++)if(p[i]==-1 || p[i]==0)dp[i][1<<i] = 0;for(int cur=0; cur<(1<<n); cur++)for(int i=0; i<n; i++)if(dp[i][cur] > -INF)for(int j=0; j<n; j++)if(p[j]==-1 || p[j]==__builtin_popcount(cur))if(!((1<<j)&cur) && i!=j)dp[j][cur|(1<<j)] = max(dp[j][cur|(1<<j)], dp[i][cur] + a[i]*a[j]);int ans = -INF;for(int i=0; i<n; i++)ans = max(ans, dp[i][(1<<n)-1]);printf("%d\n", ans);}
}

代码编程
赞赏

相关文章

零基础学习游戏建模多久能出师?3D建模师告诉你如何有效的学会建模
学3D建模一定要有美术功底?有则锦上添花,没有也不影响你学习
3D建模难学吗?零基础学6个月,能否找到工作?
3D建模入行难不难?零基础学习次世代,这6条建议能帮到你
游戏建模师薪资能给到多少?建模初学者如何快速入行,获取涨薪机会?
游戏建模行业门槛真有这么高?教你如何学习,找到合适自己的方式