首页 > 其他分享 >dp HDU - 5074

dp HDU - 5074

时间:2023-02-13 20:25:58浏览次数:49  
标签:HDU int scanf num 5074 dp 105

按题意推表达式

#include<cstdio>
#include<cstring>
#define max(a, b) (a)>(b)?(a):(b)

int dp[105][105], num[105][105], a[105];

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m;++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &num[i][j]);
        for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
        for (int i = 2; i <= n; ++i)
        {
            if (a[i - 1] > 0 && a[i] > 0)dp[i][a[i]] = dp[i - 1][a[i - 1]] + num[a[i - 1]][a[i]];
            else if (a[i - 1]<0 && a[i]>0)
            {
                for (int k = 1; k <= m; ++k)
                    dp[i][a[i]] = max(dp[i][a[i]], dp[i - 1][k] + num[k][a[i]]);
            }
            else if (a[i - 1] > 0 && a[i] < 0)
            {
                for (int k = 1; k <= m; ++k)
                    dp[i][k] = max(dp[i][k], dp[i - 1][a[i - 1]] + num[a[i - 1]][k]);
            }
            else
            {
                for (int k = 1; k <= m;++k)
                for (int j = 1; j <= m; ++j)
                    dp[i][k] = max(dp[i][k], dp[i - 1][j] + num[j][k]);
            }
        }
        int ans = 0;
        for (int i = 1; i <= m; ++i)
            ans = max(ans, dp[n][i]);
        printf("%d\n", ans);
   


 

标签:HDU,int,scanf,num,5074,dp,105
From: https://www.cnblogs.com/ALINGMAOMAO/p/17117682.html

相关文章

  • 1192:放苹果(dp + 搜索)
    这道题先用搜索写的,因为我需要先打表来寻找规律。因为数据量小所以收搜也会过#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intnum[2......
  • 1092 回文字符串(LCSL_DP)
    1092回文字符串基准时间限制:1秒空间限制:131072KB分值:10难度:2级算法题收藏关注回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串......
  • P2690 接苹果 (DP)
    补一下dp的思路:dp[i][j]表示第i分钟转j 次所得到的最大值。很容易得到这个dp的推导式。图中¢()函数表示成立为1,不成立为0的函数。#include<cmath>#include<i......
  • C - Cake HDU - 1722 (数学)
    题意:就是一个蛋糕,被分成n或者m份。问最少动几刀。看一下这个图,就知道公式了,n+m-gcd(n,m);#include<cstdio>#include<iostream>usingnamespacestd;#definelllon......
  • DP8.0安装步骤session
    [root@rx6600]#./omnisetup.sh-CM-ISTheomnisetup.shscriptdidnotcompletethelasttimeitwasrun.CellManagerstillhastobeinstalledInstallation......
  • C - Cake HDU - 1722 (数学)
    题意:就是一个蛋糕,被分成n或者m份。问最少动几刀。看一下这个图,就知道公式了,n+m-gcd(n,m);#include<cstdio>#include<iostream>usingnamespacestd;#definelllon......
  • HDU 4507 (数位dp)
    HDU4507(数位dp)题意一个数满足以下三个条件之一,则被认为与7有关。1、整数中某一位是7;2、整数的每一位加起来的和是7的整数倍;3、这个整数是7的整数倍;求区间[L,R]内......
  • dp
    121.买卖股票的最佳时机-力扣(LeetCode)classSolution{public:intmaxProfit(vector<int>&prices){intmax=0;for(inti=0;i<prices.size(......
  • HDU 3709 数位dp
    HDU3709(数位dp)题意求区间[L,R]内满足以下性质的数:选定该数的一个位置,左右两边的力矩相等,如4139,选取'3'这位,左边4×2+1×1=9×1.思路一开始想着枚举每个点来做,......
  • C - Cake HDU - 1722 (数学)
    题意:就是一个蛋糕,被分成n或者m份。问最少动几刀。看一下这个图,就知道公式了,n+m-gcd(n,m);#include<cstdio>#include<iostream>usingnamespacestd;#definelllon......