加油鸭

链接：https://ac.nowcoder.com/acm/contest/553/C
来源：牛客网

Chino的数学很差，因此Cocoa非常担心。今天，Cocoa准备教Chino和排队有关的问题。
我们总是会学各种排列组合的问题，那些题目大多数都是套路。而Cocoa不喜欢套路。
通常来说，每个人在排队的时候都会对前一个人有所意见，而如果他们排在第一个，也会颇有微词。因此，排一个尽可能让更多人满意的队伍是一件难事。
假设我们要给个人排队，，表示了排在之前一个给带来的舒适度，而就表示了排在第一位的舒适度。
通过一番模拟，Chino当然计算出了最优的方案，不过Cocoa希望Chino能计算地快一点。
题目对于Chino来说太难啦，你能帮一帮Chino吗？

第一次遇到状态压缩dp题目 最后照着答案敲还是敲错了 赶紧过来补一波题目

因为n只有18 那么一定要想到二进制表示所有的状态 想到状态压缩dp

如果只是dp[i] i的二进制下j位位1表示进队伍了 的话 那么显然是不够记录当前的所以状态 因为你不知道距离之间的排序顺序 那么我们就还需要一个状态来表示最后一位是谁了
那么就要dp[i][j] 来表示状态了

首先就是这个递推方程的边界了 边界就是只有一个人进队 且自己为队头
初始化
dp[i|(1< 无后效性是针对于第一维i来说的 j的话有后效性 但是每次转移去最优
接下来就是递推方程了 保证没有后效性 dp[i-1] 不会影响到dp[i]的最优性 接下来就是转移了
如果在i的二进制下j没有进入队伍 那么就把j当做最后一个人进队 然后就是要保证j为最后一个的时候这个值要最大 那么就和排在j前面的是谁有关系了 因为这个题目值关心两两之间的排序
就有如下递推方程

dp[i|(1< 这里的k是要在i的二进制内的！！
代码如下

#include// dp三要素  状态转移方程 无后效性 边界条件 比较一下到底是谁站在最后一位using namespace std;const int maxn = 20;int dp[maxn][maxn],a[maxn][maxn];  //dp[i][j]   i 表示有多少人进队了 j表示最后一位的是谁int main()
{int n;cin>>n;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++) cin>>a[i][j];}for(int i = 0; i < (1<>j&1)==0) // j没有进队伍 让j进队伍且排在最后面 无后效性{if(i==0) dp[i|(1<>k&1)!=0) // {dp[i|(1<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！