Dp&&백팩거푸집
5712 단어 record
void zoreonepack(int val,int cost)
{
for(int i=v;i>=cost;i--)
{
if(dp[i-cost]+val>dp[i])
{
dp[i]=dp[i-cost]+val;
}
}
}
void completepack(int val,int cost)
{
for(int i=cost;i<=v;i++)
{
dp[i]=max(dp[i],dp[i-cost]+val);
}
}
void multipack(int val,int cost,int num)
{
if(num*cost>=v)
{
completepack(val,cost);
}
else
{
int k=1;
while(k
2.O(n^2)TSP
#include
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
int n,d[1005],dp[1005][1005];
int dis(int a,int b)
{
int tmp=abs(d[a]-d[b]);
return min(tmp,360-tmp);
}
int TSP_Dp()
{
dp[2][1]=dis(1,2);
for (int i = 3; i <= n + 1; i++) {
dp[i][i-1] = INF;
for (int j = 1; j < i-1; j++) {
dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dis(i, j));
dp[i][j] = dp[i-1][j] + dis(i, i-1);
}
}
int ans = INF;
for (int i = 1; i <= n; i++)
ans = min(ans, dp[n+1][i] + dis(n+1, i));
return ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
d[1]=0;
int ans=0;
scanf("%d",&n);
for(int i=2;i<=n+1;i++)
{
int a;
scanf("%d%d",&a,&d[i]);
if(i==n+1)ans+=a*800;
ans+=10;
}
ans+=TSP_Dp();
printf("%d
",ans);
}
}
3. 가방 묶기
memset(dp,0,sizeof(dp));
for(int i=1;i<=1005;i++)
{
memset(dp2,0,sizeof(dp2));
for(int j=0;j<=1005;j++)dp2[j]=dp[j];
for(int j=0;j=a[num].cost;k--)
{
dp2[k]=max(dp2[k],dp[k-a[num].cost]+a[num].val);
}
}
for(int j=0;j<=1005;j++)dp[j]=max(dp[j],dp2[j]);
}
printf("%d
",dp[v]);
4. LCA 온라인 증대
void Dfs(int u,int from)
{
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
if(v==from)continue;
d[v]=d[u]+1;
dist[v]=dist[u]+e[i].w;
p[v][0]=u;
Dfs(v,u);
}
}
void init()
{
for(int j=1;(1<d[y])swap(x,y);
int f=d[y]-d[x];
for(int i=0;(1<=0;i--)
{
if(p[x][i]!=p[y][i])
{
x=p[x][i];
y=p[y][i];
}
}
x=p[x][0];
}
return x;
}
5. 기울기 최적화 Dp
#include
#include
using namespace std;
int que[650000];
int a[650000];
int sum[650000];
int dp[650000];
int n,m;
int A(int j,int k)
{
return (dp[j]+sum[j]*sum[j])-(dp[k]+sum[k]*sum[k]);
}
int B(int j,int k)
{
return 2*(sum[j]-sum[k]);
}
int Val(int i,int j)
{
return dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
sum[0]=0;
memset(dp,0,sizeof(dp));
memset(que,0,sizeof(que));
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
int head=0,tot=0;
que[tot++]=0;
for(int i=1;i<=n;i++)
{
while(head+1
단조 대열
for(int i=1; i<=n; i++)
{
while(s<=e&&q[s].posa[i])e--;
e++,q[e].pos=i,q[e].val=a[i];
}
6.RMQ 쿼리 구간 최대 최소값
#include
#include
#include
#include
using namespace std;
int n,q;
int maxn[200005][20];
int minn[200005][20];
void ST()
{
int len=floor(log10(double(n))/log10(double(2)));
for(int j=1;j<=len;j++)
{
for(int i=1;i<=n+1-(1<b)swap(a, b);
int len= floor(log10(double(b-a+1))/log10(double(2)));
printf("%d
",max(maxn[a][len], maxn[b-(1<
7.nlogn LIS
memset(dp,0,sizeof(dp));
memset(f,0x7f,sizeof(f));
for(int i = 1; i <= n; ++i)
{
int k = lower_bound(f + 1, f+ 1 + n, a[i]) - f;
dp[i] = k;
f[k] = a[i];
}
최장 체감 서브시퀀스
int find(int n,int key)
{
int left=0;
int right=n;
while(left<=right)
{
int mid=(left+right)/2;
if(res[mid]>key)
{
left=mid+1;
}
else
{
right=mid-1;
}
}
return left;
}
int Lis(int a[],int n)
{
int r=0;
res[r]=a[0];
r++;
for(int i=1;ia[i])
{
res[r]=a[i];
r++;
}
else
{
int loc=find(r,a[i]);
res[loc]=a[i];
}
}
return r;
}
최장 비체감
int Slove(int n)
{
int c=0;
for(int i=1; i<=n; i++)
{
int t=a[i];
if(i==1) f[++c]=t;
else
{
if(t>=f[c]) f[++c]=t;
else
{
int pos=upper_bound(f+1,f+c,t)-f;// t 。
f[pos]=t;
}
}
}
return c;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Noob용 Vinyl을 사용하여 Haskell에서 확장 가능한 레코드이 튜토리얼에서는 vinyl를 사용하여 하스켈 내에서 확장 가능한 레코드를 생성하는 방법을 보여 드리겠습니다. 이 튜토리얼은 이미 Haskell에 익숙하지만 사용법을 모르는 사람들을 대상으로 합니다vinyl. 우리는...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.