惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

博客园_首页
Exploit-DB.com RSS Feed
Exploit-DB.com RSS Feed
P
Proofpoint News Feed
G
Google Developers Blog
B
Blog
Engineering at Meta
Engineering at Meta
阮一峰的网络日志
阮一峰的网络日志
The Register - Security
The Register - Security
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
博客园 - 叶小钗
The Cloudflare Blog
The Hacker News
The Hacker News
D
Darknet – Hacking Tools, Hacker News & Cyber Security
C
CXSECURITY Database RSS Feed - CXSecurity.com
雷峰网
雷峰网
F
Fortinet All Blogs
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
H
Hackread – Cybersecurity News, Data Breaches, AI and More
酷 壳 – CoolShell
酷 壳 – CoolShell
Last Week in AI
Last Week in AI
T
Threat Research - Cisco Blogs
A
About on SuperTechFans
量子位
Recorded Future
Recorded Future
博客园 - 三生石上(FineUI控件)
H
Help Net Security
Help Net Security
Help Net Security
P
Palo Alto Networks Blog
cs.CV updates on arXiv.org
cs.CV updates on arXiv.org
T
Troy Hunt's Blog
W
WeLiveSecurity
V
Vulnerabilities – Threatpost
T
The Exploit Database - CXSecurity.com
Know Your Adversary
Know Your Adversary
Apple Machine Learning Research
Apple Machine Learning Research
Scott Helme
Scott Helme
N
News | PayPal Newsroom
AWS News Blog
AWS News Blog
D
DataBreaches.Net
Blog — PlanetScale
Blog — PlanetScale
MongoDB | Blog
MongoDB | Blog
B
Blog RSS Feed
腾讯CDC
J
Java Code Geeks
Microsoft Azure Blog
Microsoft Azure Blog
TaoSecurity Blog
TaoSecurity Blog
GbyAI
GbyAI
Y
Y Combinator Blog
Hacker News - Newest:
Hacker News - Newest: "LLM"
D
Docker

博客园 - xmx

Amazon 2面杯具 N皇后回溯 "中航文化杯" 2007 ACM/ICPC 国际大学生程序设计竞赛亚洲区域赛(南京) 一个用来练dfs的简单迷宫问题 pku 1662 还是找规律的 pku 1806 Manhattan 2025(找规律) 今天西华的比赛,啥都不说啦,相当的nice!~~~ 今天北京赛区的比赛 最近看的一些东西 The 2007 ACM Asia Programming Contest Changchun Site Internet Preliminary Contest nice 位运算果真是好东西,今天算是学到点啦^_^ FOJ月赛-2007年9月 pku 1850 前面一直没注意到某个不规范的情况,导致结果一直比标准的大...调了好久... 终于有算最长重复子串(数)的后缀数组啦,nice The 2007 ACM Asia Programming Contest - Nanjing Preliminary pku 3219 人家居然用几十B就过了,肯定有超强的规律,可是我自己找了个,挂了...只能老实算... 一道双向dp,差点超时^_^||| dp pku 1050 N和素数P,求杨辉三角第N行中能被P整除的数的个数
pku 1505 copying books(DP)
xmx · 2007-10-10 · via 博客园 - xmx

#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;

int t,k,m;
int books[510];
int dp[510][510];
int part[510];

#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))

int sum(int i,int j)
{
 int t=0,p;
 for(p=i;p<=j;p++)
  t += books[p];
 return t;
}

void cal2()
{
 int i,j,l,st;
 for(i=1;i<=k;i++)
  dp[i][1] = sum(i,k);

 dp[k][1] = books[k];

 for(i=2;i<=m;i++)
 {
  dp[k-i+1][i] = Max(books[k-i+1], dp[k-i+2][i-1]);
  j = k-i+1;
  for(l=k-i; l>=m-i+1; l--)
  {
   if(sum(l,j) <= dp[j+1][i-1])
    dp[l][i] = dp[j+1][i-1];
   else if(books[l] >= dp[l+1][i-1])
    dp[l][i] = books[l] , j = l;
   else
   {
    while(sum(l,j-1) >= dp[j][i-1])
     j--;
    dp[l][i] = Min( sum(l,j), dp[j][i-1]);
    if(dp[l][i] == dp[j][l-1])
     j--;
   }
  }
 }
}

int main()
{
 int i ,j, st;
 
 scanf("%d",&t);
 books[0]=0;
 while(t--)
 {
  scanf("%d %d",&k,&m);
  for(i=1;i<=k;i++) scanf("%d",&books[i]);
  memset(dp,0,sizeof(dp));
  cal2();

  st = 0; j = 0;
  for(i=k;i>=1;i--)
  {
   st += books[i];
   if(st > dp[1][m])
   {
    part[j++] = i+1;
    st = books[i];
   }
     if(st == dp[1][m])
   {
    if(m-j <= i)
    {
     part[j++] = i;
     st = 0;
    }
    else
    {
     part[j++] = i+1;
     st = books[i];
    }
   }
  }

  j--;
  printf("%d",books[1]);
  for(i=k;i<=2;i++)
  {
   if(i == part[j])
   {
    printf(" /");
    j--;
   }
   printf(" %d",books[i]);
  }
  printf("\n");
 }
}