acwing1388. 游戏 + LC1406.石子游戏 零和博弈

零和博弈

有点类似那个Min-Max 游戏

考虑DP【l,r】 为当前考虑到[l,r]当前的先手能得到的最大的分

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}


int n,q,m;

int a[N];
int dp[110][110];
int s[110][110];
int dfs(int l,int r){
	
	if(l==r)return a[l];
	if(~dp[l][r])return dp[l][r];
	dp[l][r] = s[l][r] - min(dfs(l+1,r),dfs(l,r-1));
	return dp[l][r];
}


void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	
	for(int l=1;l<=n;l++)
	 for(int r=l;r<=n;r++)
	 	for(int i=l;i<=r;i++)
	 	 s[l][r]+=a[i];
	 	 
	memset(dp,-1,sizeof dp);
	int t = dfs(1,n);
	int t1 = s[1][n]-t;
	cout<<t<<" "<<t1;
	
	 
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _;
	//cin>>_;
	_ = 1;
	while(_--)solve();
	return 0;
}

再看这一道很类似的题目~

class Solution {
public:
    string stoneGameIII(vector<int>& stoneValue) {
        int n = stoneValue.size();
        vector<int>s(n+10,0);
        vector<int>v(n+10,0);

        for(int i=1;i<=n;i++)v[i] = stoneValue[i-1];
        for(int i=n;i>=1;--i)s[i] = s[i+1]+v[i];

        vector<int>dp(n+10,0);

        // function<int(int u)>dfs = [&](int u){
        //     if(u>n)return 0;
        //     if(u==n)return v[u];
        //     if(~dp[u])return dp[u];
        //     dp[u] = s[u] - min({dfs(u+1),dfs(u+2),dfs(u+3)});
        //     return dp[u];
        // };

        for(int i=n;i>=1;--i){
            dp[i] = s[i]-min({dp[i+1],dp[i+2],dp[i+3]});
           // cout<<s[i]<<" "<<dp[i]<<"\n";
        }


       int t1 = dp[1];
      // cout<<t1<<"\n";
       int t2 = s[1] - t1;
       if(t1>t2)return "Alice";
       else if(t1<t2)return "Bob";
       return "Tie";



    }
};

一开始的DP 是TLE 的改成递推就好了,它是一个单端操作,可以直接改成递推

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/510856.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

NIKKI DENSO伺服驱动器维修NCR-CAB1A2D-801B

NEXSRT伺服驱动器维修NPSA-MU日机电装伺服维修ACTUS POWER&#xff0c;NCS-ZE12MDA/ZE1MDA-601A&#xff0c;NEXSRT日机电装伺服维修NCS-ZE12MDB-401A/NCS-ZAMDA-401AG。 NIKKI常见故障原因及处理方法&#xff1a; 1、电机在一个方向上比另一个方向跑得快&#xff1b; (1) 故…

4个惊艳的AI项目,开源了!

大家好&#xff0c;今天继续聊聊科技圈发生的那些事。 一、Champ 三维参数导引下可控一致的人体图像动画生成项目。只需要一张照片&#xff0c;就能让照片里的人物动起来。 给出一个动作视频&#xff0c;Champ 可以让不同的人像复刻出相同的动作。 我们先来看看真实人物照片…

【PowerDesigner】PGSQL反向工程过程已中断

问题 反向工程过程已中断,原因是某些字符无法通过ANSI–&#xff1e;UTF-16转换进行映射。pg导入sql时报错&#xff0c;一查询是power designer 反向工程过程已中断&#xff0c;某些字符无法通过ANSI–>UTF-16转换进行映射&#xff08;会导致数据丢失&#xff09; 处理 注…

生活篇——关于分期贷或信用贷的等额本息、先息后本、月利率、年利率、年利率单利的个人理解

首先我先就年利率的理解问一下各位读者2个问题。 问题1&#xff1a;假设你要借100000元&#xff0c;借一年&#xff0c;月利息0.2%&#xff0c;等额本息&#xff0c;那么你觉得你总共需要还多少利息&#xff1f;它的实际年利率约为多少&#xff1f; A.2400&#xff0c;2.4% …

C语言一维数组及二维数组详解

引言&#xff1a; 小伙伴们&#xff0c;我发现我正文更新的有些慢&#xff0c;但相信我&#xff0c;每一篇文章真的都很用心在写的&#xff0c;哈哈&#xff0c;在本篇博客当中我们将详细讲解一下C语言中的数组知识&#xff0c;方便大家后续的使用&#xff0c;有不会的也可以当…

Java设计之道:色即是空,空即是色

0.引子 我们的这个世界上&#xff0c;存在这么一种东西&#xff1a; 第一&#xff1a;它不占据任何3D之体积&#xff0c;即它没有Volume第二&#xff1a;它也不占据任何2D之面积&#xff0c;即它没有Area第三&#xff1a;它也不占据任何1D之长度&#xff0c;即它没有Length 总…

《QT实用小工具·三》偏3D风格的异型窗体

1、概述 源码放在文章末尾 可以在窗体中点击鼠标左键进行图片切换&#xff0c;项目提供了一些图片素材&#xff0c;整体风格偏向于3D类型&#xff0c;也可以根据需求自己放置不同的图片。 下面是demo演示&#xff1a; 项目部分代码如下所示&#xff1a; 头文件部分&#xff…

NULL与nullptr的区别

NULL是宏定义&#xff0c;如下&#xff1a; 如果用NULL&#xff0c;在函数重载时&#xff0c;NULL的类型被推断为int。这是不好的&#xff0c;所以引入nullptr。nullptr是c11引入的关键字&#xff0c;它就代表空指针。

idea、pycharm、datagrip2023版全家桶安装+激活+性能优化

前序 内容&#xff1a;在windows11环境&#xff0c;以idea为例教大家安装、激活idea、pycharm、datagrip2023最新版本全家桶并性能优化 一、下载安装JDK 1、下载JDK 官网链接&#xff1a;https://www.oracle.com/java/technologies/downloads/archive 下载需要注册账户&…

每日一题:用c语言写(输入n个数(n小于等于100),输出数字2的出现次数)

目录 一、要求 二、代码 三、结果 ​四、注意 一、要求 二、代码 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> int main() {//输入n个数&#xff08;n小于等于100&#xff09;&#xff0c;输出数字2的出现次数;int n[100] ;int num 0;int count 0;/…

【面试HOT200】链表篇

系列综述&#xff1a; &#x1f49e;目的&#xff1a;本系列是个人整理为了秋招面试coding部分的&#xff0c;整理期间苛求每个算法题目&#xff0c;平衡可读性与代码性能&#xff08;leetcode运行复杂度均打败80%以上&#xff09;。 &#x1f970;来源&#xff1a;材料主要源于…

分享几个可以免费使用的GPT网站吧

1. ChatGAI ChatGAI是一个界面简洁的AI平台&#xff0c;提供App和网页版&#xff0c;每日均有免费使用机会。 2. ChatGPT 本网站向大家开放了ChatGPT 3.5和4.0版本的免费体验&#xff0c;特别适合新用户。每天都有免费次数&#xff0c;响应迅速&#xff0c;注册便捷&#xff0…

Java基础核心Map

在Java中&#xff0c;Map是一种用于存储键值对&#xff08;key-value pairs&#xff09;的集合类型。它提供了一种将键映射到值的方式&#xff0c;其中每个键在Map中都是唯一的。Map接口是java.util包中的一部分。 常用实现类&#xff1a; HashMap: 基于哈希表实现的Map&#…

db2 使用jdbc建立连接时,指定schema,schema不存在也会连接成功

使用db2想指定schema&#xff0c;使用语句如下 jdbc:db2://" hostname ":" port "/" databaseName ":currentSchema" this.databaseSchema ";"; 切记&#xff1a;最后的分号一定要有&#xff0c;否则报错。 但是此处有…

C++11---右值引用(深度讲解)

简要介绍 右值引用是C11的新特性,无论左值引用还是右值引用&#xff0c;都是在给对象取别名 什么是左值 什么是右值 1.左值,左值引用 左值是一个数据的表达式(例如变量或者解引用后的指针),我们可以对其进行取地址和修改赋值,左值可以出现在赋值符号的左边,而右值不能出现在…

算法打卡day32|贪心算法篇06|Leetcode 738.单调递增的数字、968.监控二叉树

算法题 Leetcode 738.单调递增的数字 题目链接:738.单调递增的数字 大佬视频讲解&#xff1a;单调递增的数字视频讲解 个人思路 这个题目就是从例子中找规律&#xff0c;例如 332&#xff0c;从后往前遍历&#xff0c;32不是单调递增将2变为9,3减1&#xff0c;变成了329&…

【Django开发】前后端分离美多商城项目第5篇:用户部分,起源【附代码文档】

美多商城项目4.0文档完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;美多商城&#xff0c;项目准备1.B2B--企业对企业,2.C2C--个人对个人,3.B2C--企业对个人,4.C2B--个人对企业,5.O2O--线上到线下,6.F2C--工厂到个人。项目准备&#xff0c;配置1. 修改set…

Kubernetes(k8s):部署、使用 metrics-server

Kubernetes&#xff08;k8s&#xff09;&#xff1a;部署、使用 metrics-server 一、metrics-server简介二、部署metrics-server2.1、 下载 Metrics Server 部署文件2.2、修改metrics-server.yaml 文件2.3、 部署 Metrics Server2.4、 检查 Metrics Server 三、使用 Metrics Se…

Boost之Log: (3)、简单封装

设计目标: 1、每个Logging source对应一个目录&#xff0c;可以设置日志文件数&#xff0c;日志大小&#xff0c;目录名&#xff0c;文件名等 2、所有logging source日志目录都在一个根目录下。 3、可以动态创建和删除logging source 4、打印出日期时间和日志严重等级 示例代码…

从python角度解析selenium原理

1、selenium工作流程 2、selenium工作原理 &#xff08;1&#xff09;客户端和服务端之间实际是通过http协议进行通信&#xff0c;服务端的接口文档可参考&#xff1a;https://github.com/SeleniumHQ/selenium/wiki/JsonWireProtocol#sessionsessionidelement &#xff08;2&…