【2022年11月19日提高A组】消圈策略【DP】
创始人
2024-02-01 21:25:52
0

在这里插入图片描述

思路:

dis i 代表1 到 i 的最短路
因为它要求没有负环
无负环和可以求出最短路是充要条件
然后dis i 和 dis (i+1)相差最多不超过1
因为有0边的存在
然后就对边的大小进行分类讨论
如果i 那么dis (i) - 1 >= dis j
然后移项
dis i - dis j >= 1
这个式子代表的意思就是i到j这之间所有的边都要删掉
然后如果i>j即e i,j 是1
那么dis (i) + 1 >= dis j
移项
dis j - dis i <= 1
这意味着从[i,n]到[1,j]的所有边都要删掉
我们设fi = disi - dis(i+1),然后这绝对是一个非负数。。而且值只能是0或1,因为根据上面那个dis j - dis i <= 1,用fi表示就是fj + f(j+1)+……+f(i-1)<=1,所以我们就可以考虑构造fi
因为fj + f(j+1)+……+f(i-1)<=1,所以我们想到设dp[i][j]表示最后的两个1在i和j这里的最小删边代价
然后转移就是dp[i][j]=min(d[i][j],dp[j][k]+{从[i,n]到[1,j)的边的价值和} + {从[j,i) 到 [j,i) 的边的价值和})
然后中间那个价值和在循环里用前缀和求

codecodecode

#include
#include
#include
#define ll long longusing namespace std;const ll MAXN = 505;ll n;
ll a[MAXN][MAXN], sum[MAXN][MAXN], sum2[MAXN][MAXN], dp[MAXN][MAXN];int main() {scanf("%lld", &n);for(ll i = 1; i <= n; i ++) {for(ll j = 1; j <= n; j ++) {if(i == j) continue;scanf("%lld", &a[i][j]);}}n ++;memset(dp, 0x7f, sizeof(dp));dp[0][0] = 0;for(ll i = 1; i < n; i ++) {for(ll j = 0; j < i; j ++) {for(ll k = i + 1; k <= n; k ++)sum[i][j] += a[k][j];if(j) sum[i][j] += sum[i][j - 1];}for(ll j = i - 1; j >= 0; j --) {for(ll k = j + 1; k <= i; k ++)sum2[i][j] += a[j + 1][k];if(j + 1 < i - 1) sum2[i][j] += sum2[i][j + 1];}for(ll j = 0; j < i; j ++) {for(ll k = 0; k <= j; k ++)dp[i][j] = min(dp[i][j], dp[j][k] + sum[i][j] - sum[i][k] + sum2[i][j]);} }ll ans = 1e18;for(ll i = 0; i < n; i ++)ans = min(ans, dp[n - 1][i]);printf("%lld", ans);return 0;
}

相关内容

热门资讯

喜欢穿一身黑的男生性格(喜欢穿... 今天百科达人给各位分享喜欢穿一身黑的男生性格的知识,其中也会对喜欢穿一身黑衣服的男人人好相处吗进行解...
发春是什么意思(思春和发春是什... 本篇文章极速百科给大家谈谈发春是什么意思,以及思春和发春是什么意思对应的知识点,希望对各位有所帮助,...
网络用语zl是什么意思(zl是... 今天给各位分享网络用语zl是什么意思的知识,其中也会对zl是啥意思是什么网络用语进行解释,如果能碰巧...
为什么酷狗音乐自己唱的歌不能下... 本篇文章极速百科小编给大家谈谈为什么酷狗音乐自己唱的歌不能下载到本地?,以及为什么酷狗下载的歌曲不是...
华为下载未安装的文件去哪找(华... 今天百科达人给各位分享华为下载未安装的文件去哪找的知识,其中也会对华为下载未安装的文件去哪找到进行解...
怎么往应用助手里添加应用(应用... 今天百科达人给各位分享怎么往应用助手里添加应用的知识,其中也会对应用助手怎么添加微信进行解释,如果能...
家里可以做假山养金鱼吗(假山能... 今天百科达人给各位分享家里可以做假山养金鱼吗的知识,其中也会对假山能放鱼缸里吗进行解释,如果能碰巧解...
四分五裂是什么生肖什么动物(四... 本篇文章极速百科小编给大家谈谈四分五裂是什么生肖什么动物,以及四分五裂打一生肖是什么对应的知识点,希...
一帆风顺二龙腾飞三阳开泰祝福语... 本篇文章极速百科给大家谈谈一帆风顺二龙腾飞三阳开泰祝福语,以及一帆风顺二龙腾飞三阳开泰祝福语结婚对应...
美团联名卡审核成功待激活(美团... 今天百科达人给各位分享美团联名卡审核成功待激活的知识,其中也会对美团联名卡审核未通过进行解释,如果能...